Hay un caballo en un tablero de ajedrez de n x n. Para cada casilla, imprime el número mínimo de movimientos que el caballo necesita hacer para llegar a la esquina superior izquierda.

Entrada

La única línea tiene un entero n.

Salida

Imprime el número de movimientos para cada casilla.

Restricciones

• ~4 \leq n \leq 1000~

Ejemplo de Entrada

8

Ejemplo de Salida

0 3 2 3 2 3 4 5
3 4 1 2 3 4 3 4
2 1 4 3 2 3 4 5
3 2 3 2 3 4 3 4
2 3 2 3 4 3 4 5
3 4 3 4 3 4 5 4
4 3 4 3 4 5 4 5
5 4 5 4 5 4 5 6