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.

输入输出样例

输入样例 #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

说明

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

**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。**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。