Description

N 皇后问题是一个经典的问题。

输入 $N$，你需要求出在一个 $N\times N$ 的棋盘中，放置 $N$ 个皇后，使得皇后两两不互相威胁的所有方案。

两个皇后互相威胁，当且仅当它们在同一行或或一列或同一条斜线上。参考国际象棋中的皇后。

Format

Input

仅一行一个数 $N\,(1\leq N\leq 12)$.

Output

第一行输出 $K$ 表示有 $K$ 种不同的方案。然后，输出 $K$ 行，每行输出 $N$ 个数 $p_1,p_2,\ldots,p_N$ 表示第一行的皇后放在第 $p_1$ 列，第二行的皇后放在第 $p_2$ 列……第 $N$ 行的皇后放在第 $N$ 列。可以证明不会有一行放两个皇后的情况。

若有多种方案，可以按任意顺序输出。两个方案不同当且仅当这两个方案对应的数列 $p_1,p_2,\ldots,p_N$ 不同。

若没有方案，则仅在第一行输出 $0$ 即有 $0$ 种不同的方案即可。

Samples

2

-1

6

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

Limitation

1s, 32MiB.

本题开启所有数据捆绑测试：即所有的数据都 AC 本题得到满分，否则不得分。