会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将n个皇后放在棋盘上（有n× n个方格），使它们谁也不能被吃掉！这就是著名的n皇后问题。对于某个满足要求的n皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...bn，其中bi为相应摆法中第i行皇后所处的列数.

### 输入格式:

一个整数n，表示棋盘大小。

### 输出格式:
输出所有满足要求的解，每行一个答案。最后输出一个数，表示一共有多少个解。

###

会下国际象棋的人都很清楚：皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将n个皇后放在棋盘上（有n× n个方格），使它们谁也不能被吃掉！这就是著名的n皇后问题。对于某个满足要求的n皇后的摆放方法，定义一个皇后串a与之对应，即a=b1b2...bn，其中bi为相应摆法中第i行皇后所处的列数.

### 输入格式:

一个整数n，表示棋盘大小。

### 输出格式:
输出所有满足要求的解，每行一个答案。最后输出一个数，表示一共有多少个解。

### 输入样例:


in
4


### 输出样例:



out
2 4 1 3
3 1 4 2
2







答案：若无答案欢迎评论