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.