題意：

有一個 n×n 的矩陣（n 為奇數），每個矩陣單元有一個物品，每次操作你可將一個單元里的一個物品移動到該單元周圍的八個單元里，問最后只有一個單元有物品的情況下，最少要多少次操作？

題目：

You are given a board of size n×n, where n is odd (not divisible by 2). Initially, each cell of the board contains one figure.

In one move, you can select exactly one figure presented in some cell and move it to one of the cells sharing a side or a corner with the current cell, i.e. from the cell (i,j) you can move the figure to cells:

(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);
Of course, you can not move figures to cells out of the board. It is allowed that after a move there will be several figures in one cell.

Your task is to find the minimum number of moves needed to get all the figures into one cell (i.e. n2?1 cells should contain 0 figures and one cell should contain n2 figures).

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1≤t≤200) — the number of test cases. Then t test cases follow.

The only line of the test case contains one integer n (1≤n<5?105) — the size of the board. It is guaranteed that n is odd (not divisible by 2).

It is guaranteed that the sum of n over all test cases does not exceed 5?105 (∑n≤5?105).

Output

For each test case print the answer — the minimum number of moves needed to get all the figures into one cell.

Example

Input

3
1
5
499993

Output

0
40
41664916690999888

分析(1)：

找規律。可以看到正方形的每一個“圈”到中心的最小距離都是一樣的（數一下就能發現規律）。然后把整個正方形分成八個小三角形+八條線或者直接按照圈來統計都行。

AC代碼

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; typedef long long ll; int t; ll n,ans; int main() {scanf("%d",&t);while(t--){ans=0;scanf("%lld",&n);for(ll i=2; i<=n/2+1; i++)ans+=(i-2)*(i-1);ans*=8;for(ll i=1; i<=n/2+1; i++)ans+=(i-1)*8;printf("%lld\n",ans);}return 0; }

分析（二）

我們可以將所有物品最終都匯聚到矩陣的中心的單元格，那么以此為中心，他周圍的第一圈的單元格的物品只需要一步就可以，第二圈就需要兩步，以此類推。
??那么我們可以預處理出每一圈的單元格的數量，乘以他對應的步數，再求和即可。

AC代碼

#include <bits/stdc++.h> using namespace std; const int N = 5e5 + 10; typedef long long ll; int f[N]; int main() {f[0] = 0;for(int i = 1; i < N; i ++)f[i] = f[i - 1] + 8;int t;cin >> t;while(t --){ll n;cin >> n;n = n * n - 1;ll ans = 0;for(int i = 1; ; i ++){if(n >= f[i]){n -= f[i];ans += 1ll * i * f[i];}elsebreak;}cout << ans << endl;}return 0; }

總結

以上是生活随笔為你收集整理的Board Moves CodeForces - 1353C（数学）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。