Фермер решил на своем квадратном участке земли вспахать пашню квадратной формы максимальной площади, т.к. он посчитал, что именно квадратная форма пашни наиболее удобна для обработки. Но на его участке присутствуют деревья и хозяйственные постройки, которые он никуда не хочет переносить, а так же иные места, не пригодные для пашни. Для удобства он составил квадратную карту местности N×N в форме матрицы и пометил нулями непригодные для пашни зоны, в остальные зоны он поставил единицу.
В первой строке входного файла INPUT.TXT записано единственное натуральное число N (1 ≤ N ≤ 1000) – длина стороны квадратного участка фермы. Далее, следует N строк, в каждой из которых находится последовательность (без пробелов) нулей и единиц, описывающих ферму.
В выходной файл OUTPUT.TXT необходимо вывести максимально возможную площадь пашни.
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 7
1101101
1111110
1011100
0011100
1000010
1100111
1001110
| 9 |
