#2833. 数列对计数

内存限制:256 MiB 时间限制:10 Sec

题目描述

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

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

交换AB

A的每个数减一常数,B的每个数加一常数;

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

所以,你可以认为a[1]=0b[1]=1A,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<=1000。