Matcom Online Grader

Luego de años de mucho trabajo, los científicos han inventado una nueva pantalla electrónica. La nueva pantalla tiene mayor resolución, consume menos energía y es más barata de producir. Además se puede doblar. El único inconveniente es su inusual forma de operar. Por esa razón los desarrolladores decidieron dejar el desarrollo de programas para esta pantalla a los programadores.

La pantalla se representa como un cuadrado de pixeles de n x n, donde cada uno puede ser blanco o negro. Las filas están numeradas desde 1 hasta n de arriba a hacia abajo, las columnas están numeradas desde 1 hasta n de izquierda a derecha. La pantalla puede procesar comandos como “x, y”. Cundo una pantalla tradicional procesa este comando, simplemente invierte el color del pixel (x, y), donde x es la fila y y es la columna. Pero en la nueva pantalla cada pixel que pertenezca a al menos uno de los segmentos (x, x) – (x, y) y (y, y) – (x, y) (los extremos están incluidos) invierten su color.

Por ejemplo, si inicialmente una pantalla de 5 x 5 está absolutamente en blanco, entonces la secuencia de comandos (1, 4), (3, 5), (5, 1), (3, 3) provoca los siguientes cambios:

Usted está programando una de estas pantallas y deberá calcular el mínimo número de comandos que se necesitan para mostrar una imagen. Al inicio todos los pixeles estarán en blanco.

Input

La primera línea contiene un número n (1 ≤ n ≤ 2000). Las siguientes n líneas contienen n caracteres cada una: la descripción de la imagen que deberá ser mostrada. 0 representa el color blanco y  el negro.

Output

Imprima un entero que es el menor número de comandos para mostrar la imagen.

Sample test(s)