Migrated from Lutece 1984 New N皇后问题

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在一个 $n\times n$ 的棋盘中，放任意数量的'假'皇后，这些'假'皇后只能攻击上下左右相邻的'假'皇后，问有多少种放法让这些皇后不相互冲突？

Input

第一行：一个整数 $T\ (T \leq 10)$ 表示数据的组数；

接下来有 $T$ 行，每行一个整数 $n\ (1 \le n \le 10)$。

Output

共 $T$ 行，每行为放法的答案数。

Samples

3
1
2
3

2
7
63

Resources

2018 UESTC ACM Training for Search Algorithm and String