XOR로 그림 그리기

흑백 화면을 쓰는 휴대폰 애플리케이션을 만들고 있다. 화면의 x좌표는 왼쪽에서, y좌표는 위에서 센다. 애플리케이션에는 크기가 제각각인 그림이 여러 장 필요한데, 그림을 저장해 두는 대신 휴대폰의 그래픽 라이브러리로 그때그때 그리려고 한다. 그림을 그리기 시작할 때 화면의 픽셀은 모두 흰색이다.

라이브러리가 제공하는 연산은 XOR(L,R,T,B) 하나뿐이다. 이 연산은 왼쪽 위 좌표가 (L,T)이고 오른쪽 아래 좌표가 (R,B)인 직사각형 안의 픽셀 값을 모두 뒤집는다. L은 왼쪽, T는 위, R은 오른쪽, B는 아래 좌표다. 다른 그래픽 라이브러리는 인자 순서가 이와 다를 수 있으니 주의한다.

Figure-3의 그림을 예로 들어 보자. 모두 흰색인 화면에 XOR(2,4,2,6)을 적용하면 Figure-1이 되고, 여기에 XOR(3,6,4,7)을 적용하면 Figure-2가 되며, 마지막으로 XOR(1,3,3,5)를 적용하면 Figure-3이 된다.

Figure-1	Figure-2	Figure-3

같은 그림도 그리는 방법은 여러 가지다. 위 예는 직사각형을 마음대로 고를 수 있을 때 세 번의 호출로 Figure-3을 그린 것이다. 이 문제에서는 고를 수 있는 직사각형이 제한된다. 모든 호출이 화면의 오른쪽 아래 끝에 닿아야 한다. 즉 R과 B는 항상 $N$이다.

이 제한 아래에서는 같은 호출을 두 번 하면 화면이 처음으로 돌아가므로, 주어진 그림을 그리는 호출의 집합이 정확히 하나로 정해진다. 그 집합의 크기, 곧 그림을 그리는 데 필요한 호출의 최소 횟수를 구하시오.

첫 줄에 그림의 행과 열의 개수 $N$이 주어진다. ($5 \le N \le 2000$)

다음 $N$개의 줄은 그림의 행을 위에서 아래 순서로 나타낸다. 각 줄에는 정수 $N$개가 왼쪽 픽셀부터 순서대로 주어지며, 0은 흰색 픽셀, 1은 검은색 픽셀이다.

그림을 그리는 데 필요한 XOR 호출의 최소 횟수를 한 줄에 출력한다.