---

凭直觉（并且可以证明），最佳策略是将每个棋子移动到中心格子 $\left(\frac{n+1}{2}, \frac{n+1}{2}\right)$。通过一些简单的计算或观察，我们可以注意到：

• 恰好有 $8$ 个格子的最短距离为 $1$，
• 有 $16$ 个格子的最短距离为 $2$，
• 有 $24$ 个格子的最短距离为 $3$，
• 依此类推。

因此，距离为 $i$ 的格子有 $8i$ 个。所以答案为：

$$1 \cdot 8 + 2 \cdot 16 + 3 \cdot 24 + \dots + \left(\frac{n-1}{2}\right)^2 \cdot 8 $$

这可以改写为：

$$8 \left( 1^2 + 2^2 + 3^2 + \dots + \left(\frac{n-1}{2}\right)^2 \right) $$

因此，我们只需计算从 $1$ 到 $\frac{n-1}{2}$ 的所有整数的平方和（可以使用循环，或者使用公式 $\frac{k(k+1)(2k+1)}{6}$），然后将结果乘以 $8$。

令 $k = \frac{n-1}{2}$，则答案为：

$$\text{答案} = 8 \times \frac{k(k+1)(2k+1)}{6} = \frac{4 \cdot k(k+1)(2k+1)}{3} $$

时间复杂度：$O(n)$ 或 $O(1)$。

---

#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int t;
	cin >> t;
	while (t--) {
		int n;
		cin >> n;
		long long ans = 0;
		for (int i = 1; i <= n / 2; ++i) {
			ans += i * 1ll * i;
		}
		cout << ans * 8 << endl;
	}
	
	return 0;
}