find-the-treasure

Ross is an archaeologist. He is leading a team that recently found an ancient place. They could collect few information about this place like maps and scripts. The map they found has only 1s and 0s. 

From the scripts they found, they got to know that this map resembles the place and there is a treasure buried under the area which is represented as a diagonal matrix of equal side lengths in the map. Some other script mentioned that it should be the largest possible matrix.

Ross and his team is finding it difficult to find that in the map and contacted you for help. Find the dimension of largest diagonal matrix.

Input format:

First line has T denoting number of test cases.
Each test case starts with two integers in first line M,N denoting rows and columns in the map/matrix.
M lines follows with N integers separated with a space.

Output format:

Print a single integer denoting side length of largest possible diagonal matrix in given matrix.

Constraints:

1 ≤ T ≤ 50
1 ≤ M,N ≤ 500
0 ≤ A[i][j] ≤ 1

Problem Setter: Vinay Kumar

SAMPLE INPUT
2
5 5
1 1 1 1 1
1 0 1 1 0
1 1 1 0 1
1 1 0 1 1
1 0 1 1 0
4 5
1 1 0 0 0
0 1 0 0 1
0 0 1 0 1
0 0 0 1 0

SAMPLE OUTPUT
2
3

Source: hackerearth | Difficulty: UNKNOWN_DIFFICULTY
Tags: Dynamic programming


Solutions: