题目描述

游戏工作室“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$ 的正方形吗？

输入格式

每个测试点包含多个测试用例。第一行包含测试用例数 $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$。

输出格式

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

说明/提示

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

在第二个测试用例中，我们只能选择边长为 $1$ 的正方形，所以答案是 $1$。

在第三个测试用例中，没有边长为 $2$ 的正方形能满足所有建筑高度至少为 $2$，所以答案是 $1$。

由 ChatGPT 4.1 翻译

样例

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

2
1
1
3