HZNUOJ

Triangles

Tags:
Time Limit:  1 s      Memory Limit:   256 MB
Submission:138     AC:69     Score:98.08

Description

又到了白色相簿的季节。

Alice非常喜欢白色相簿2,并且认为三角形是最稳定也是最优美的图形。

Alice发现了一个N-三角形,N-三角形由$N*(N+1)/2$个边长均为1的小等边三角形组成,这些小三角形同向组成了N-三角形。

下图是一个3-三角形示例

Alice想找出N-三角形中所有顶点构成的子等边三角形数量,子等边三角形的每一边可以不平行于N-三角形中的一边。

下图是N-三角形的两个子等边三角形示例

Input

第一行给出一个正整数$T$,表示有T组数据$(1 \leq T \leq 1000)$

接下来的T行中,每一行给出一个正整数$N$,表示N-三角形的度数$(1 \leq N \leq 50000)$


Output

对于每一个测试用例,在一行中输出一个整数,代表N-三角形中的子等边三角形数量

数据可能会很大,建议使用long long而不是int

Samples

input
3 1 2 3
output
1 5 15

Hint


Author

HU, Haoquan