P15708 [JAG 2023 Summer Camp #2] 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.

$$ \begin{aligned} &T \\ &N_1 \\ &N_2 \\ &\vdots \\ &N_T \end{aligned} $$ The input satisfies the following constraints. - All inputs consist of integers. - $1 \leq T \leq 10^5$ - $3 \leq N_i \leq 10^9$

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.

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