/*
 * First idea:
 * There are three possibilities for the number of positions you can be in, in a reahable square (one direction, three directions, all directions)
 * After the first four moves, the result for n+1 is a linear combination of the result for n.
 * Speed this up using maxtrix exponentiation.
 * Complexity: O(log(n))
 */

#include <cstdio>
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)

typedef long long ll;

ll A[32][4][4];
ll B[2][4][4];

void run() {
	int n; scanf("%d",&n);
	switch(n) {
		case 0: printf("%d\n",1); return;
		case 1: printf("%d\n",2); return;
		case 2: printf("%d\n",5); return;
	}
	
	n-=3;
	int a=0,b=1;
	REP(i,4) REP(j,4) B[a][i][j]=i==j?1:0;
	
	FOR(x,1,32) if(n&(1<<(x-1))) {
		a=1-a; b=1-b;
		REP(i,4) REP(j,4) { B[a][i][j]=0; REP(k,4) B[a][i][j]+=B[b][i][k]*A[x][k][j]; }
	}
	
	ll ret=0;
	FOR(i,1,4) ret+=1*B[a][i][0]+6*B[a][i][1]+3*B[a][i][2]+2*B[a][i][3];
	printf("%lld\n",ret);
}

void precalc() {
	REP(i,4) REP(j,4) A[0][i][j]=i==j?1:0;
	REP(i,4) REP(j,4) A[1][i][j]=0; A[1][0][0]=1; A[1][1][0]=4; A[1][1][1]=1; A[1][2][1]=1; A[1][3][2]=1; A[1][3][3]=1;
	FOR(x,2,32) REP(i,4) REP(j,4) { A[x][i][j]=0; REP(k,4) A[x][i][j]+=A[x-1][i][k]*A[x-1][k][j]; }
}

int main() {
	precalc();
	
	int n; scanf("%d",&n); REP(i,n) run();
	
	return 0;
}

