소 뒤집기

농부 존은 밤마다 농장에 찾아와 소를 넘어뜨리고 가는 심심한 십대들 때문에 가끔 골치를 앓는다. 어느 날 아침 일어나 보니 또 같은 일이 벌어져 있었다. 존의 소 $N^2$마리는 $N \times N$ 크기의 완벽한 정사각형 격자 모양으로 서서 밤을 맞았는데($1 \le N \le 10$), 지금은 그중 일부가 넘어져 있다.

다행히 존은 트랙터와 지게차 부품으로 여러 마리의 소를 한꺼번에 뒤집는 멋진 기계 Cow-Untipperator 3000을 만들어 두었다. 이 기계로 모든 소를 최대한 빨리 다시 일으켜 세울 수 있다. 존은 소 격자의 "왼쪽 위 직사각형"이라면 어디에든 기계를 적용할 수 있다. 왼쪽 위 직사각형은 가장 왼쪽 위에 있는 소를 포함하는 직사각형 모양의 부분 격자이다. 기계를 적용하면 그 직사각형 안의 소가 모두 뒤집힌다. 넘어진 소는 다시 일어서지만, 아쉽게도 서 있던 소는 넘어진다. 즉 기계는 직사각형 안에 있는 각 소의 상태를 반전시킨다.

존은 알맞은 직사각형들에 기계를 충분히 여러 번 적용하면 결국 모든 소를 넘어지지 않은 원래 상태로 되돌릴 수 있다고 생각한다. 이를 위해 기계를 적용해야 하는 최소 횟수를 구해 존을 도와주자.

같은 직사각형에 기계를 두 번 적용하면 그 직사각형 안의 소에 아무 변화도 없으므로 의미가 없다. 따라서 각 왼쪽 위 직사각형에는 기계를 최대 한 번만 적용한다고 생각하면 된다.

첫째 줄에 정수 $N$이 주어진다. ($1 \le N \le 10$)

다음 $N$개의 줄에는 각각 길이 $N$인 문자열이 주어진다. 각 문자는 0(서 있는 소) 또는 1(넘어진 소)이다.

모든 소를 다시 일으켜 세우기 위해 존이 Cow-Untipperator 3000을 적용해야 하는 최소 횟수를 출력한다.

첫 번째 예제에서 존이 소 무리 전체(이것도 올바른 왼쪽 위 직사각형이다)에 기계를 적용하면 상태가 다음과 같이 바뀐다.

110
000
000

이제 1 두 개를 포함하는 왼쪽 위 직사각형에 기계를 적용하면 끝난다. 모두 합쳐 2번만 적용하면 된다.