要求在n*n格的棋盘上放置彼此不会相互攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

### 输入格式:
测试数据有多组，处理到文件尾。对于每组测试，输入棋盘的大小n（1<n<12）。

### 输出格式:
对于每组测试，输出满足要求的方案个数。

### 输入样例:
in
4



### 输出样例:
out
2

要求在n*n格的棋盘上放置彼此不会相互攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

### 输入格式:
测试数据有多组，处理到文件尾。对于每组测试，输入棋盘的大小n（1<n<12）。

### 输出格式:
对于每组测试，输出满足要求的方案个数。

### 输入样例:
in
4



### 输出样例:
out
2







答案：若无答案欢迎评论