2
1
2

3
7
直接DFS + 打表过，比较水

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int MAXN  = 20 + 5;
LL M[MAXN << 2][MAXN << 2],dp[MAXN];
bool vis[MAXN << 2][MAXN << 2];
int C, n;
void dfs(int pos,int x,int y){
    if(pos > 16) return;
    if(vis[x][y]) return;
    dp[pos] ++;
    vis[x][y] = true;
    dfs(pos + 1,x + 1, y);
    dfs(pos + 1,x, y + 1);
    dfs(pos + 1,x, y - 1);
    vis[x][y] = false;
}
void init(){
    memset(dp, 0, sizeof(dp));
    memset(vis,false,sizeof(vis));
    dp[20]=54608393;
    dp[19]=22619537;
    dp[18]=9369319;
    dp[17]=3880899;
    dfs(0,0,50);
}
int main(){
    init();
    scanf("%d", &C);
    while(C --){
        scanf("%d", &n);
        printf("%I64d\n",dp[n]);
    }
    return 0;
}