Drawing with XOR

You are writing an application for a mobile phone with a black and white screen. The x coordinate of the screen starts at the left and the y coordinate starts at the top. The application needs many pictures of different sizes. Instead of storing them, you want to draw each one with the phone's graphics library. When drawing starts, every pixel of the screen is white.

The library has one operation, XOR(L,R,T,B). It flips every pixel value inside the rectangle whose top left corner is (L,T) and whose bottom right corner is (R,B). Here L is the left coordinate, T the top, R the right, and B the bottom. Other graphics libraries may take these arguments in a different order.

Take the picture in Figure-3 as an example. Applying XOR(2,4,2,6) to an all white screen gives Figure-1. Applying XOR(3,6,4,7) to Figure-1 gives Figure-2, and applying XOR(1,3,3,5) to Figure-2 gives Figure-3.

Figure-1	Figure-2	Figure-3

The same picture can be drawn in many ways. The example above picks its rectangles freely and draws Figure-3 with three calls. This problem restricts the rectangles you may call: every call has to reach the bottom right corner of the screen, so R and B are always $N$.

Under that restriction, making the same call twice returns the screen to its earlier state, so exactly one set of calls draws a given picture. Find the size of that set, the smallest number of calls that draws the picture.

The first line contains $N$, the number of rows and columns of the picture. ($5 \le N \le 2000$)

Each of the next $N$ lines describes one row of the picture, from top to bottom. A line contains $N$ integers, the pixel values from left to right, where 0 is a white pixel and 1 is a black pixel.

Print the smallest number of XOR calls that draws the picture.