Дивани

Limits: 2 sec., 256 MiB

Зеник і Марічка роблять ремонт у вітальні.

Марічка приготувала план розміщення усіх меблів, окрім дивану. Це завдання вона доручила Зенику, який дуже любить дивани, і хоче розмістити їх якомога більше.

Кімната має квадратний розмір і складається із \(n \times n\) одиничних квадратів. План розташування меблів можна зобразити у вигляді матриці \(A\) із \(n\) рядків та \(n\) стовпців, де значення \(A_{ij}\) рівне 1, якщо відповідний одиничний квадрат вже заповнений меблями, або 0 якщо ні.

Зеник хоче розмістити якомога більше диванів розміру \(1 \times (n-1)\) або \((n-1) \times 1\). Ваше завдання — допомогти йому знайти цю найбільшу кількість.

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

Input

У першому рядку задано одне ціле число \(n\) — розмір стін.

У наступних \(n\) рядках задано по \(n\) символів 0 або 1 в кожному, без пробілів — матриця \(A\). Символ 1 означає, що відповідний квадрат зайнятий, 0 — вільний.

Output

У єдиному рядку виведіть одне ціле число — максимальну кількість диванів.

Constraints

\(3 \le n \le 50\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 111 000 000	3

Input (stdin) сopy	Output (stdout) сopy
3 000 100 101	3

Input (stdin) сopy	Output (stdout) сopy
4 0000 0000 0000 0000	5

Notes

У першому прикладі оптимально розмістити три дивани наступним чином (однакові букви позначають позиції дивану):

У другому прикладі також можна розмістити три дивани:

У третьому прикладі можна розмістити 5 диванів: