题目描述

考虑两个数列整数列 $A=\{a_1,a_2,\dots,a_n\}$ 和 $B=\{b_1,b_2,\dots,b_n\}$,如果从两个数列中各取一项 $a_i$ 和 $b_j$，其和各不相同且全部在 $[1,n^2]$ 内，则称 $(A,B)$ 是一个数列对。求本质不同的数列对数。

如果两个数列对在进行以下操作或以下若干操作的组合后相同，那么则认为他们是本质相同的：

1. 交换 $A$ 和 $B$。
2. $A$ 的每个数减一常数，$B$ 的每个数加一常数。
3. 交换 $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$ 个：

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

数据规模与约定

对于 $100\%$ 的数据，$n\le1000$。