说明

在n×n的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之在同一行、同一列、同一斜线上的棋子。设计算法在n×n的棋盘上放置n个皇后，使其彼此不受攻击。

输入格式

第一行是一个整型数C(C<100)表示共有C组测试数据。

每组测试数据只有一行，输入皇后数n（1<=n<=10）。

输出格式

对于每一组输入，输出有多少种皇后放置方案。

每组的输出占一行。

样例

2
4
10

2
724

来源

《趣学算法》5.5节