A15462 | Valiant's New Map

Game studio "DbZ Games" wants to introduce another map in their popular game "Valiant". This time, the map named "Panvel" will be based on the city of Mumbai.

Mumbai can be represented as $n \times m$ cellular grid. Each cell $(i, j)$ ( $1 \le i \le n$ ; $1 \le j \le m$ ) of the grid is occupied by a cuboid building of height $a_{i,j}$ .

This time, DbZ Games want to make a map that has perfect vertical gameplay. That's why they want to choose an $l \times l$ square inside Mumbai, such that each building inside the square has a height of at least $l$ .

Can you help DbZ Games find such a square of the maximum possible size $l$ ?

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$ .

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