На решетке размером N×N некоторые ее узлы покрашены в белый, а некоторые – в черный цвет. Необходимо определить число квадратов, которые возможно получить таким образом, что их вершины будут совпадать с узлами заданной решетки и будут покрашены в одинаковый цвет.
Например, на рисунке 1 изображена решетка размером 4×4 и на ней существует ровно 1 такой квадрат, который показан на рисунке 2:
Первая строка входного файла INPUT.TXT содержит целое число N – размер решетки (2 ≤ N ≤ 50). Следующие N строк содержат по N чисел из множества {0, 1} и задают решетку. Если точка с координатами (i, j) покрашена в белый цвет, то j-ое число i-ой строки равно 0, в противном случае – это 1.
В выходной файл OUTPUT.TXT выведите количество квадратов на решетке.
№ | INPUT.TXT | OUTPUT.TXT |
1 | 4
0 1 0 0
0 0 1 1
1 0 0 0
0 1 1 1
| 1 |
2 | 4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
| 20 |