说明

Micchan 注意到，从上方看时，一把雨伞是一个正多边形。因此，她创造了以下问题。

雨伞查询

一个正 $N$ 边形有 $N$ 条边和 $\frac{N(N-1)}{2} - N$ 条对角线。考虑它们的并集，其中包含 $\frac{N(N-1)}{2}$ 条线段。

有多少对线段满足以下两个条件？

• 这两条线段有一个公共端点。换句话说，它们在正 $N$ 边形的某个顶点处有一个公共点。
• 这两条线段互相垂直。

Micchan 给出了 $T$ 个上述问题。然而，她的朋友无法解决太多的请求。请代表她回答每个问题。

输入格式

$$\begin{aligned} &T \\ &N_1 \\ &N_2 \\ &\vdots \\ &N_T \end{aligned}$$

输入满足以下约束：

• 所有输入均为整数。
• $1 \leq T \leq 10^5$
• $3 \leq N_i \leq 10^9$

输出格式

输出 $T$ 行答案。在第 $i$ 行，输出当 $N = N_i$ 时问题的答案。每行末尾请添加换行符。

3
4
3
1000000000

4
0
499999999000000000

提示

在样例输入 1 中，你只需要计算在正方形的顶点处垂直相交的线段对。

翻译由 DeepSeek V3.2 完成