在学习了今天的课程以后，tyx也对N皇后问题产生了兴趣，可惜他想了很久还是不知道怎么写，于是又一次抱住你的大腿请求你的帮助。
他想知道对于 的棋盘，最多有多少种满足条件的摆法？
所谓满足条件的摆法，即每一行、每一列、每一条对角线最多仅能有一个皇后。
当然，tyx为了确保你不是随便报了一个数字来忽悠他，他需要你给出按照字典序从小到大排序的前 组解（如果不足 种，则全部输出）。
一个解的序列是这样的定义的：设 表示第 行的皇后放在了第 列的位置，其中 ，那么这个解所对应的的序列就是 。
注意，tyx非常讨厌数学好的人，因此你如果直接用公式计算出了答案，tyx可能会打死你。