说明

设n≡1(mod 4)（n除以4余1）且n>1,设P={a1,a2,…,an}是{1,2,3,…n}的任意排列，k是对应排列P使下列不等式成立的最大下标i,a1+a2+…+ai<ai+1+…+an.试对一切可能的不同排列P，求对应的最大下标k值之和。

输入格式

首行输出一个正整数T，代表有T组数据。接下来T行每行一个正整数n(2 < n < 1000)。

输出格式

按要求输出答案，每组数据输出一行。

2
5
89

240
699550161

来源

2013 校程序设计竞赛