Max Black Square

You are given a square matrix with N rows and N columns, in which each cell (pixel) is either black or white. The black pixels are represented as ‘1’ and the white pixels are represented as ‘0’.

Design an algorithm to find the maximum length of a sub-square of the matrix such that all four borders are filled with black pixels.

Input Format

The first line of input contains an integer ‘T' representing the number of test cases.

The first line of each test case contains one integer ‘N’ denoting the size of the matrix.

The next ‘N’ lines contain ‘N’ integers separated by spaces describing rows of the matrix. (each element of the matrix is either 0 or 1).

Output Format:

For each test case, on a separate line, output one integer - the maximum length of a side of a subsquare such that all four borders are filled with black pixels.

Note :

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 10^3
MATRIX[i][j] = 0 or 1

Where ‘T’ is the number of test cases, ‘N’  is the size of the given array, and ‘MATRIX[i][j]’ denotes the j’th element of the i’th row of the matrix "MATRIX".

Time Limit: 1 sec