"Fl!ps" es un videojuego (de creación original) en el que se tiene un tablero de ~8 \times 8~ (~64~) casillas, que pueden ser de color blanco o negro. Al comenzar la partida, se elige un color al azar para todas las ~64~ casillas del tablero. En cada turno, el jugador puede escoger una casilla e invertir el color de dicha casilla, además de invertir el color de las cuatro casillas adyacentes. El objetivo es conseguir que todas las casillas del tablero sean del mismo color, ya sea blanco o negro.

Formalmente, al escoger la casilla ~(x, y)~ (~1 \le x, y \le 8~), se invertirá el color de las ~5~ casillas ~(x, y)~, ~(x + 1, y)~, ~(x - 1, y)~, ~(x, y - 1)~, ~(x, y + 1)~, siempre y cuando estas se encuentren dentro del tablero (una casilla ~(x', y')~ está dentro del tablero si ~1 \le x', y' \le 8~).

Aunque el videojuego original utilizase un tablero de ~8 \times 8~ casillas, ¿podrías, dado un tablero de ~n \times n~ casillas, determinar el número mínimo de movimientos necesarios para alcanzar el objetivo propuesto?

Entrada

La primera línea contendrá un entero: ~n~ (~1 \le n \le 5 \cdot 10^{4}~), el número de filas y columnas que tiene el tablero en cuestión.

Las siguientes ~n~ líneas contendrán ~n~ enteros: ~a_{i, j}~ (~0 \le a_{i, j} \le 1; 0 \mathrel{:=} \text{blanco}; 1 \mathrel{:=} \text{negro}~), el color de la casilla ~(i, j)~ (~1 \le i, j \le n~).

Salida

Se ha de imprimir un entero ~m~, el número mínimo de movimientos necesarios para que todas las casillas del tablero sean del mismo color.

Puntuación

• 30 puntos: ~n \le 5~
• 70 puntos: Sin restricciones.