Description

考虑两个数列整数列A = {a[1], a[2], …, a[n]} and B = {b[1], b[2], …, b[n]},如果从两个数列中各取一项a[i]和b[j]，其和各不相同且全部在[1,n*n]内，则称(A,B)是一个数列对。求本质不同的数列对数。

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

交换A和B；

A的每个数减一常数，B的每个数加一常数；

交换A中或B中任意两个数。

所以，你可以认为a[1]=0，b[1]=1，A,B均按升序排列。

Format

Input

第一行一个整数T表示测试数据个数；

以下T行每行一个整数n表示序列的长度。

Output

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

Samples

4

1

2

3

4

1

1

1

3

Limitation

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<=1000。