数列对计数

考虑两个整数序列

$$A=\{a_1,a_2,\ldots,a_n\},\qquad B=\{b_1,b_2,\ldots,b_n\}。$$

若分别从两个序列中任取一项 $a_i$ 和 $b_j$，得到的 $n^2$ 个和 $a_i+b_j$ 两两不同，且均在区间 $[1,n^2]$ 内，则称 $(A,B)$ 为一个数列对。

如果两个数列对经过以下一种或若干种操作后能够变得相同，则认为它们本质相同：

• 交换 $A$ 和 $B$；
• 将 $A$ 中的每个数减去同一个常数，同时将 $B$ 中的每个数加上该常数；
• 交换 $A$ 或 $B$ 中任意两个数的位置。

因此，可以认为 $a_1=0$、$b_1=1$，且 $A$、$B$ 均按升序排列。

请计算本质不同的数列对数量。

输入格式

第一行输入一个整数 $T$，表示测试数据的组数。

接下来 $T$ 行，每行输入一个整数 $n$，表示序列的长度。

输出格式

对于每组测试数据，输出一行一个整数，表示本质不同的数列对数量。

样例输入

4

1

2

3

4

样例输出

1
1
1
3

样例解释

当 $n=4$ 时，共有 $3$ 个本质不同的数列对：

• $A=\{0,1,2,3\}$，$B=\{1,5,9,13\}$；
• $A=\{0,1,4,5\}$，$B=\{1,3,9,11\}$；
• $A=\{0,1,8,9\}$，$B=\{1,3,5,7\}$。

数据范围

• 对于 $100\%$ 的数据，$n\le 1000$。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 1

输入

4

1

2

3

4

输出

1
1
1
3