数列对计数

时间限制:10s      空间限制:256MB

题目描述

考虑两个数列整数列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。

 


题目来源

没有写明来源