← 返回题目列表

Codeforces · 1731/D

D. Valiant 的新地图

中文机器翻译题面 查看原题

游戏工作室“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$$$。