### #Description

A knight jumps around an infinite chessboard. The chessboard is an unexplored territory. In the spirit of explorers, whoever stands on a square for the first time claims the ownership of this square. The knight initially owns the square he stands, and jumps $N$ times before he gets bored. Recall that a knight can jump in 8 directions. Each direction consists of two squares forward and then one squaure sidways.

After $N$ jumps, how many squares can possibly be claimed as territory of the knight? As $N$ can be really large, this becomes a nightmare to the knight who is not very good at math. Can you help to answer this question?

### #input

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.
Each test case contains only one number $N$, indicating how many times the knight jumps.
$1 \leq T \leq 10^5$,$0 \leq N \leq 10^9$

### #output

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is the number of squares that can possibly be claimed by the knight.

### #source 2017 CCPC FINAL

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
// 打表推公式
int a[]={1,9,41,109,205,325,473};
int main() {
int t;scanf("%d", &t);
for(int kase=1; kase<=t; kase++){
ll n;scanf("%lld", &n);
printf("Case #%d: ", kase);
if(n<=6) {
printf("%d\n",a[n]);
continue;
}
printf("%llu\n",176 * (n-6) + (n-6) * (n-7) * 14 + 473);
}
return 0;
}


#include<bits/stdc++.h>
int dir[][2]={{-2,1},{-1,2},{1,2},{2,1},{1,-2},{2,-1},{-2,-1},{-1,-2}};
struct node{
int x, y, steps;
};
const int maxn = 1111;
int ans[maxn];
bool vis[maxn][maxn];
void bfs() {
queue<node> q;
q.push(node{500,500,0});
ans[0] = 1;
vis[500][500] = 1;
while(!q.empty()){
node cur = q.front(); q.pop();
if(cur.steps == 20) continue;
for(int i=0; i<8; i++){
node nxt = cur;
nxt.x += dir[i][0], nxt.y += dir[i][1];
if(vis[nxt.x][nxt.y]) continue;
vis[nxt.x][nxt.y] = 1;
ans[++nxt.steps] ++;
q.push(nxt);
}
}
}
int main() {
bfs(); int ret = 0;
for(int i=0;i<=20;i++) printf("%d ", ans[i]);puts("");
for(int i=0;i<20;i++) printf("%d ", (ret+=ans[i])); puts("");
for(int i=1;i<20;i++) printf("%d ",ans[i]-ans[i-1]);
for(int i=7;i<=20;i++) printf("%d ",176 * (i-6) + (i-6) * (i-7) / 2 * 28 + 473);
}