游戏工作室“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$$$。
示例
输入 #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
输出 #1
2 1 1 3
注意
在第一个测试用例中,我们可以选择边长 $$$l = 2$$$ 的正方形(即整个网格),因为所有建筑物的高度都大于或等于 $$$2$$$。
在第二个测试用例中,我们只能选择边为$$$1$$$,所以答案是$$$1$$$。
在第三个测试用例中,不存在 $$$2$$$ 大小的正方形中所有建筑物的高度至少为 $$$2$$$,因此答案为 $$$1$$$。