Опрокидывание коров

У Фермера Джона появилась проблема с тинэйджерами, которые залезали на ферму ночью и опрокидывали коров. Однажды утром это случилось опять. Некоторые из его n^2 коров которые паслись на квадратном пастбище n * n, оказались опрокинутыми.

У ФД есть машина, которая может поставить на ноги сразу всех коров, которые были опрокинуты, из указанного прямоугольника, правда при этом она опрокидывает всех коров из этого прямоугольника, которые стояли. То есть, машина переключает состояние кажэдой коровы из этого прямоугольника.

Помогите ФД определить минимальное количество применений машины, чтобы все коровы оказались в не опрокинутом положении.

Заметим, что применение машины в однмо и том же прямоугольнке дважды бесполезно, поскольку не изменит состояние коров в этом прямоугольнике.

Входные данные

Первая строка содержит целое число n (1 ≤ n ≤ 10). Каждая из последующих строк содержит строку из n (0 - не опрокинутая корова, 1 - опрокинутая корова).

Выходные данные

Выведите минимальное количество раз, которое ФД должен применить машину, чтобы все коровы оказались не опрокинутыми.

Примеры

Примечание

В этом примере, если ФД применит свою машину ко всем коровам, он получит следующее

110
000
000

Затем можно применить машину двум верхним единицам. Итого два применения машины.