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

游戏工作室“DbZ Games”希望在他们热门游戏《Valiant》中新增一张地图。本次地图名为“Panvel”，其设计灵感来源于孟买市。

孟买可被建模为一个 $n \times m$ 的网格。网格中每个单元格 $(i, j)$（其中 $1 \le i \le n$，$1 \le j \le m$）上均矗立着一座长方体建筑，其高度为 $a_{i,j}$。

此次，DbZ Games 希望打造一张具备完美垂直玩法的地图。因此，他们希望在孟买网格内选出一个 $l \times l$ 的正方形区域，使得该正方形内每一座建筑的高度均至少为 $l$。

你能帮助 DbZ Games 找出满足条件的最大可能边长 $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$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \leq t \leq 1000$）。随后是测试用例的描述。

每个测试用例的第一行包含两个正整数 $n$ 和 $m$（$1 \le n \le m$；$1 \leq n \cdot m \leq 10^6$）。

接下来的 $n$ 行中，第 $i$ 行包含 $m$ 个整数 $a_{i,1}, a_{i,2}, \dots, a_{i,m}$（$1 \leq a_{i,j} \leq 10^6$），表示第 $i$ 行各建筑物的高度。

保证所有测试用例的 $n \cdot m$ 之和不超过 $10^6$。

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

对于每个测试用例，输出 DbZ Games 可选择的正方形的最大边长 $l$。

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

在第一个测试用例中，我们可以选择边长为 $l = 2$ 的正方形（即整个网格），因为所有建筑物的高度均大于或等于 $2$。

在第二个测试用例中，我们只能选择边长为 $1$，因此答案为 $1$。

在第三个测试用例中，不存在大小为 $2$ 且所有建筑物高度均至少为 $2$ 的正方形，因此答案为 $1$。