题目描述

小爱 有一张 $n$ 行 $m$ 列的整数网格，格子 $(i, j)$ 上的数 $a_{i, j}$ 表示该处的建筑高度。

请找出最大的整数 $l$，使得存在一个 $l \times l$ 的子正方形，其中每个格子上的数都大于等于 $l$。

形式化地说，要找到最大的 $l$，使得存在 $r, c$ 满足 $1 \le r$、$r + l - 1 \le n$、$1 \le c$、$c + l - 1 \le m$，且对所有 $r \le i \le r + l - 1$ 与 $c \le j \le c + l - 1$ 都有 $a_{i, j} \ge l$。

输入格式

从文件 tower.in 读入数据。

输入的第一行包含一个正整数 $t$，表示测试数据组数。

接下来依次给出 $t$ 组数据，每组数据的格式为：

第一行包含两个正整数 $n$ 与 $m$，表示网格的行数与列数，保证 $n \le m$。

接下来 $n$ 行，每行 $m$ 个整数，其中第 $i$ 行的第 $j$ 个数是 $a_{i, j}$。

输出格式

输出到文件 tower.out。

对于每组数据，输出一行一个整数，表示满足条件的最大边长 $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

2
1
1
3

样例 1 解释

第一组数据里取整个 $2 \times 2$ 网格，四个格子上的数都大于等于 $2$，所以答案是 $2$。

第二组数据是 $1 \times 3$ 的网格，取边长 $1$ 的正方形（例如格子 $a_{1,1} = 1 \ge 1$）满足条件。

第三组数据里可以取边长 $1$ 的正方形，例如格子 $a_{1,1} = 4 \ge 1$。

第四组数据里可以取第 $1 \sim 3$ 行、第 $2 \sim 4$ 列构成的 $3 \times 3$ 区域，内部的数都大于等于 $3$。

样例 2&3

见附件

数据范围

对于所有测试数据，保证：

• $1 \le t \le 1000$；
• $1 \le n \le m$，$1 \le n \cdot m \le 10^6$；
• $1 \le a_{i, j} \le 10^6$；
• 单个测试文件中所有测试用例的 $n \cdot m$ 之和不超过 $10^6$。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。