Шахматных дел мастера
...И он подошел ко дворцу и увидел, что ворота его
открыты, и, войдя в ворота, он увидел в проходе каменную скамью, а
на скамье – двух девушек, подобных луне, перед которыми стояла
шахматная доска, и они играли.
"Тысяча и одна ночь", "Сказка о Хасане басрийском"
Рассказывают также, что был в древние времена и минувшие века и столетия повелителя правоверных Харун ар-Рашид узнал о такой игре как шахматы. И повелел он тогда плотникам вырезать доску и фигуры, красильщикам – покрасить их в белый и красный цвет, и лакировщикам - покрыть их лаком.
И сделали они так, и принесли затем доску повелителю. Однако клетки доски были окрашены совсем не в шахматном порядке. Тогда потребовал Харун ар-Рашид объяснения от красильщика. И говорил мастер такое, что на шахматной доске, какой квадрат из клеток ни возьми (со сторонами параллельными сторонам доски), в нем обязательно количество красных и белых клеток будет отличаться друг от друга не больше, чем на 1. На той доске, которую он сделал, не обязательно все квадраты будут с таким свойством, но многие.
Заинтересовали повелителя правоверных речи красильщика (хоть и не спасли последнего от казни), и он захотел узнать во скольких различных квадратах на доске, изготовленной красильщиком, разность между количеством красных и белых клеток не более 1.
Входные даные
В первой строке задается размер доски N (1 ≤ N ≤ 300). В последующих N строках записаны по N чисел, каждое из которых определяет цвет соответствующей клетки доски (0 - белая, 1 - красная).
Выходные даные
В единственной строке выведите количество квадратов доски с указанным свойством.