Сова Соня подарила ёжику Филе огромный пазл размером n на m с изображением красивого озера. Друзья сразу начали собирать картинку, но много фрагментов пазла оказались пустыми — на них не было никакого рисунка. Фрагменты с рисунком будем обозначать числом 1, а пустые фрагменты — числом 0. Строки пазла пронумерованы сверху вниз целыми числами от 1 до n, а столбцы — слева направо целыми числами от 1 до m.
Зверята решили сложить картину полностью и немного поиграть с ней, ведь это же еще интереснее! Сова и ёжик по очереди задают друг другу вопросы. Вопрос определяется четырьмя числами x1, y1, x2, y2, которые описывают прямоугольник, где (x1, y1) — координаты левой верхней клетки прямоугольника, а (x2, y2) — координаты правой нижней клетки. Ответом на вопрос является максимальный размер квадрата, полностью сложенного из фрагментов с рисунками (то есть квадрата из 1) и полностью находящегося внутри прямоугольника из вопроса.
Помогите Соне и Филе ответить на t запросов.
Выходные данные
Выведите t строк. В i-й из них выведите максимальную длину стороны квадрата, полностью состоящего из 1 и лежащего внутри запроса.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4
1 1 0 1
0 1 1 0
0 1 1 0
5
1 1 2 3
2 1 3 2
3 2 3 4
1 1 3 4
1 2 3 4
|
1
1
1
2
2
|