D. Новая карта Valiant
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Разработчик игр «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$$$).

В $$$i$$$-й из следующих $$$n$$$ строк заданы $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно число — наибольший размер $$$l$$$ квадрата, который может выбрать DbZ Games.

Пример
Входные данные
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
Примечание

В первом наборе входных данных мы можем выбрать квадрат со стороной $$$l = 2$$$ (т. е. все поле), так как высоты всех зданий больше или равны $$$2$$$.

Во втором наборе мы можем выбрать сторону квадрата только как $$$1$$$, а потому ответ равен $$$1$$$.

В третьем наборе на поле нет квадратов со стороной $$$2$$$, в которых все здания не ниже $$$2$$$, а потому ответ равен $$$1$$$.