• A
• B
• C
• D
• E
• F
• G
• H
• I
• J
• K

Triangles 2690

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

Hint