Coloca \(n\) reinas en un tablero de \(n \times n\) de modo que ninguna ataque a otra: no puede haber dos en la misma fila, columna o diagonal. Encuentra todas las formas de hacerlo.

Cada solución tiene exactamente una reina por fila, así que se describe con \(n\) números: la columna (de \(1\) a \(n\)) de la reina de cada fila, de la primera a la última.

Entrada

Un entero \(n\) \((1 \le n \le 9)\).

Salida

La primera línea tiene la cantidad de soluciones. Siguen las soluciones, una por línea, en orden lexicográfico de sus \(n\) columnas.

Ejemplo 1

Entrada

4

Salida

2
2 4 1 3
3 1 4 2

Ejemplo 2

Entrada

1

Salida

1
1