Problem Statement

Micchan noticed that an umbrella looks like a regular polygon when viewed from above. She then created the following problem.

Umbrella Query

A regular $N$-gon has $N$ edges. It also has $\frac{N(N-1)}{2} - N$ diagonals. Consider the set of these $\frac{N(N-1)}{2}$ line segments in total.

How many pairs of $2$ line segments in this set satisfy both of the following $2$ conditions?

• The $2$ line segments have a common endpoint. (That is, they share a point at a vertex of the $N$-gon.)
• The $2$ line segments are perpendicular to each other.

Micchan has posed $T$ of the above problems. However, Micchan's friend cannot keep up with so many requests. On her behalf, find the answer to each problem.

Input

$T$
$N_1$
$N_2$
$\vdots$
$N_T$

• All inputs are integers.
• $1 \le T \le 10^5$
• $3 \le N_i \le 10^9$

Output

Output the answers over $T$ lines.
On the $i$-th line, output the answer to the problem for $N = N_i$.
End each line with a newline.

Sample

3
4
3
1000000000

4
0
499999999000000000