C. 棋盘移动

每次测试的时间限制：$1$ 秒
内存限制：$256$ 兆字节

你有一个大小为 $n \times n$ 的棋盘，其中 $n$ 是奇数（不能被 $2$ 整除）。初始时，棋盘的每个格子中都放有一个棋子。

在一次移动中，你可以选择某个格子中的一个棋子，将其移动到与该格子共边或共角的相邻格子中。也就是说，从格子 $(i, j)$ 出发，你可以将棋子移动到以下格子：

• $(i-1, j-1)$
• $(i-1, j)$
• $(i-1, j+1)$
• $(i, j-1)$
• $(i, j+1)$
• $(i+1, j-1)$
• $(i+1, j)$
• $(i+1, j+1)$

当然，你不能将棋子移动到棋盘之外。允许在一次移动后，同一个格子中有多个棋子。

你的任务是：找出将所有棋子集中到同一个格子中所需的最少移动次数（即最终有 $n^2 - 1$ 个格子没有棋子，一个格子有 $n^2$ 个棋子）。

你需要回答 $t$ 个独立的测试用例。

输入

第一行包含一个整数 $t$（$1 \le t \le 200$）—— 测试用例的数量。接下来是 $t$ 个测试用例。

每个测试用例仅有一行，包含一个整数 $n$（$1 \le n < 5 \cdot 10^5$）—— 棋盘的大小。保证 $n$ 是奇数（不能被 $2$ 整除）。

同时保证所有测试用例的 $n$ 之和不超过 $5 \cdot 10^5$（$\sum n \le 5 \cdot 10^5$）。

输出

对于每个测试用例，输出答案 —— 将所有棋子集中到一个格子中所需要的最少移动次数。

示例

输入：

3
1
5
499993

输出：

0
40
41664916690999888