Valiant 的新地图

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定一个 $n\times m$ 的网格，第 $(i,j)$ 个格子的建筑高度为 $a_{i,j}$。

你需要选择一个边长为 $l$ 的正方形区域，使该正方形内每座建筑的高度都不小于 $l$。求最大的可行边长 $l$。

输入格式

第一行包含一个整数 $t$（$1\le t\le1000$）。

每个测试用例的第一行包含两个整数 $n,m$（$1\le n\le m$，$nm\le10^6$）。

接下来 $n$ 行，每行包含 $m$ 个整数 $a_{i,j}$（$1\le a_{i,j}\le10^6$）。

所有测试用例的 $n\cdot m$ 之和不超过 $10^6$。

输出格式

对每个测试用例输出一行最大可行边长。

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

数据范围