Разработчик игр «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.
42 22 34 51 31 2 32 34 4 32 1 45 61 9 4 6 5 810 9 5 8 11 624 42 32 8 11 123 1 9 69 13 313 22 60 12 14 17
2 1 1 3
В первом наборе входных данных мы можем выбрать квадрат со стороной $$$l = 2$$$ (т. е. все поле), так как высоты всех зданий больше или равны $$$2$$$.
Во втором наборе мы можем выбрать сторону квадрата только как $$$1$$$, а потому ответ равен $$$1$$$.
В третьем наборе на поле нет квадратов со стороной $$$2$$$, в которых все здания не ниже $$$2$$$, а потому ответ равен $$$1$$$.
Название |
---|