Дивани

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 диванів: