Перекидання корів

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

Фермер Джон має машину, яка може одночасно поставити на ноги всіх перекинутих корів у заданому прямокутнику, але при цьому вона також перекидає всіх корів, які стояли в цьому прямокутнику. Тобто, машина змінює стан кожної корови в цьому прямокутнику.

Допоможіть фермеру Джону визначити мінімальну кількість застосувань машини, щоб усі корови опинилися в неперекинутому положенні.

Зверніть увагу, що застосування машини в одному і тому ж прямокутнику двічі не має сенсу, оскільки це не змінить стан корів у цьому прямокутнику.

Вхідні дані

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

Вихідні дані

Виведіть мінімальну кількість разів, яку фермер Джон повинен застосувати машину, щоб усі корови опинилися в неперекинутому стані.

Приклади

Примітка

У цьому прикладі, якщо фермер Джон застосує свою машину до всіх корів, він отримає наступне:

110
000
000

Потім можна застосувати машину до двох верхніх одиниць. Усього два застосування машини.