题目描述

小新有一个大小为 N×N 且仅由 0 和 1 构成的矩阵 A，他希望通过最少次数的操作把整个矩阵内的数字全部变成 0。

每次操作，小新可以选择矩阵内的任意一个位置 (x, y) (1 ≤ x, y ≤ N)，并把以坐标 (1, 1) 作为左上角，以坐标 (x, y) 作为右下角的这个子矩阵内的每个数字进行 0/1 互换，即 0 变成 1，1 变成 0。

请问小新达成目标所需要的最少操作次数是多少次？

输入格式

第一行包含一个正整数 N。

接下来 N 行，第 i 行包含 N 个整数 A[i][1] A[i][2] ... A[i][N]，表示 A 矩阵第 i 行的各个数字。

测试样例

输入样例：

3
001
111
111

输出样例：

2

说明

0 ≤ A[i][j] ≤ 1

对于 32% 的数据： N ≤ 5

对于 48% 的数据： N ≤ 100

对于 100% 的数据： 1 ≤ N ≤ 2000

限制

时间限制：1000 ms

内存限制：65536 KB