题目描述

要在国际象棋棋盘中放 $n$ 个皇 后（棋盘大小为 $n * n$ ），使任意两个皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一对角线的任意棋子。）

输入输出格式

输入

输入一行，包含一个正整数 $n（n <= 9）$。

输出

如果存在符合条件的放置方法，输出所有解，每组解占一行，其中每个数字占 5 个字符宽度，右对齐；如果不存在符合条件的解，则输出“no solute!”（不包含引号）。

样例

输入1

4

输出1

2    4    1    3
3    1    4    2

解释1

如下图所示，当n=4时，皇后放置的两种解法： 解法1：第一行的2列，第二行的4列，第三行的1列，第四行的3列。组成一起就是2 4 1 3 解法2：第一行的3列，第二行的1列，第三行的4列，第四行的2列。组成一起就是3 1 4 2