Umbrella Queries

Micchan noticed that an umbrella is a regular polygon when looking from above. So, she created the following problem.

Umbrella Query

A regular $N$ polygon has $N$ edges and $\frac{N(N-1)}{2} - N$ diagonals. Consider the union of them, which includes $\frac{N(N-1)}{2}$ line segments.

How many pairs of line segments satisfy the following $2$ conditions?

• The $2$line segments have a common endpoint. In other words, they have a common point at one of the vertices of the regular $N$ polygon.
• The $2$ line segments are perpendicular.

Micchan has given $T$ of the above problems. However, her friend cannot solve too many requests. Answer each problem on her behalf.

$T$

$N_1$

$N_2$

$\vdots$

$N_T$

Output the answer in $T$ lines. On the $i$-th line, output the answer to the problem when $N = N_i$. Add a new line at the end of each line.

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

In Sample Input 1, you count only pairs of line segments that intersect perpendicularly at the vertices of the square.