Разработчик игр «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\)?
Выходные данные
Для каждого набора входных данных выведите одно число — наибольший размер \(l\) квадрата, который может выбрать DbZ Games.
Примечание
В первом наборе входных данных мы можем выбрать квадрат со стороной \(l = 2\) (т. е. все поле), так как высоты всех зданий больше или равны \(2\).
Во втором наборе мы можем выбрать сторону квадрата только как \(1\), а потому ответ равен \(1\).
В третьем наборе на поле нет квадратов со стороной \(2\), в которых все здания не ниже \(2\), а потому ответ равен \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|