Darko 的四元组
暂无测试数据。
Darko 是一个喜欢数数的女孩子，她喜欢和蒜头在一起玩♂游戏。
对于一个无向图，定义一个点的四元组弱连通的充要条件是四个点中有且仅有一对点有边相连。
给定 $T$ 组询问，请你构造出一个 $n$ 个点的无向图，使得无序弱连通四元组的个数最大，输出最大个数。
输入格式
输入共 $T+1$ 行。
第 $1$ 行输入 $1$ 个正整数 $T$。
接下来输入共 $T$ 行，每行输入 $1$ 个正整数 $n$ 表示询问。
输出格式
输出共 $T$ 行 $T$ 个正整数，第 $i$ 行输出第 $i$ 个询问的答案。
数据规模与约定
对于所有数据，$T\leq 5$，$n\leq 10^9$。数据点设置如下：
| 数据编号 | 特殊限制 |
|---|---|
| 1 | $T=1$，$n=4$ |
| 2,3 | $T=1$，$n\leq 8$ |
| 4,5 | $T=1$，$n\leq 15$ |
| 6,7 | $T=1$，$n\leq 30$ |
| 8,9 | $T=1$，$n\leq 50$ |
| 10,11,12 | $n\leq 300$ |
| 13,14,15,16 | $n\leq 10^6$ |
| 17,18,19,20 | $T=1$，$n$ 是质数 |
| 21,22,23,24,25 | 无特殊限制 |
5
4
25
120
114514
1919810
1
7668
4769280
4126925400472443294
326019148430562348900120