题目描述

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.

3
4
3
1000000000

4
0
499999999000000000

提示

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