Valiant's New Map

Description:

Input:

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \leq t \leq 1000$$$). Description of the test cases follows.

The first line of each test case contains two positive integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le m$$$; $$$1 \leq n \cdot m \leq 10^6$$$).

The $$$i$$$-th of next $$$n$$$ lines contains $$$m$$$ integers $$$a_{i,1}, a_{i,2}, \dots, a_{i,m}$$$ ($$$1 \leq a_{i,j} \leq 10^6$$$) — heights of buildings on the $$$i$$$-th row.

It's guaranteed that the sum of $$$n \cdot m$$$ over all test cases doesn't exceed $$$10^6$$$.

Output:

For each test case, print the maximum side length $$$l$$$ of the square DbZ Games can choose.

Sample Input:

4
2 2
2 3
4 5
1 3
1 2 3
2 3
4 4 3
2 1 4
5 6
1 9 4 6 5 8
10 9 5 8 11 6
24 42 32 8 11 1
23 1 9 69 13 3
13 22 60 12 14 17

Sample Output:

2
1
1
3

Note:

In the first test case, we can choose the square of side $$$l = 2$$$ (i. e. the whole grid) since the heights of all buildings are greater than or equal to $$$2$$$.

In the second test case, we can only choose the side as $$$1$$$, so the answer is $$$1$$$.

In the third test case, there are no squares of size $$$2$$$ that have all buildings of height at least $$$2$$$, so the answer is $$$1$$$.