Problem3812--E-reader Display

3812: E-reader Display

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

After years of hard work scientists invented an absolutely new e-reader display. The new display has a larger resolution, consumes less energy and its production is cheaper. And besides, one can bend it. The only inconvenience is highly unusual management. For that very reason the developers decided to leave the e-readers' software to programmers.

The display is represented by n×n square of pixels, each of which can be either black or white. The display rows are numbered with integers from 1 to n upside down, the columns are numbered with integers from 1 to n from the left to the right. The display can perform commands like "x,y". When a traditional display fulfills such command, it simply inverts a color of (x,y), where x is the row number and y is the column number. But in our new display every pixel that belongs to at least one of the segments (x,x)-(x,y) and (y,y)-(x,y) (both ends of both segments are included) inverts a color.

For example, if initially a display 5×5 in size is absolutely white, then the sequence of commands (1,4), (3,5), (5,1), (3,3) leads to the following changes:

You are an e-reader software programmer and you should calculate minimal number of commands needed to display the picture. You can regard all display pixels as initially white.

Input

The first line contains number n (1≤n≤2000).

Next n lines contain n characters each: the description of the picture that needs to be shown. "0" represents the white color and "1" represents the black color.

Output

Print one integer z − the least number of commands needed to display the picture.

Examples
Input
5
01110
10010
10001
10011
11110
Output
4

Source/Category