While waiting for his pan to warm up so he can cook his favourite breakfast, eggs and eggs, Sharmin decides to play a little game with the egg shells. He takes the egg shells and breaks them into small pieces, and forms a ~N~ by ~N~ grid. The egg shells Sharmin uses are orange on one side and white on the other.

Sharmin initially places the shells randomly, not caring about which coloured side is facing up. His goal is to make the entire grid white.

He decides to play a game he likes to call Cascade. If he decides to flip cell ~(i, j)~ (one-indexed), he will also flip all cells ~(x, y)~ for ~x>i~ and ~x-i\ge|y-j|~. Flipping the white cell will make it orange and vice versa.

Determine the minmum number of flips Sharmin needs to make to make the entire grid white.

Constraints

~1 \le N \le 2000~

Input Specification

The first line will contain ~N~.

The next ~N~ lines will contain ~N~ letters denoting the ~i^{th}~ row of Sharmin's egg shell grid. 0 stands for the white side facing up and 1 stands for the orange side facing up.

Output Specification

Output the minimum number of flips to make the entire grid white. In other words, the entire grid is 0.

Sample Input 1

5
00000
00000
00010
10111
11111

Sample Output 1

3

Sample Explanation

Sharmin should flip ~(3, 4)~. Then flip ~(4, 1)~. Then finally, flip ~(5, 2)~.

Sample Input 2

6
010101
111011
001101
111111
001111
111111

Sample Output 2

21