#include <iostream>

#include <cstdio>

using namespace std;

typedef long long ll;

struct matrix{

    int r,c;ll m[5][5];

};

matrix A,B,C,D;

int n;

void init(){

    A.m[1][1]=3;A.m[1][2]=1;

    B.m[1][1]=1;B.m[1][2]=1;

    B.m[2][1]=-1;B.m[2][2]=0;

    A.r=1;A.c=2;

    B.r=2;B.c=2;

}

void multyply(matrix &A,matrix B){

    int i,j,k;

    if(A.c!=B.r) printf("err\n");

    for(i=1;i<=A.r;++i){

        for(j=1;j<=B.c;++j){

            C.m[i][j]=0;

            for(k=1;k<=A.c;++k){

                C.m[i][j]+=A.m[i][k]*B.m[k][j];

            }

        }

    }

    A.c=B.c;

    for(i=1;i<=A.r;++i){

        for(j=1;j<=B.c;++j){

            A.m[i][j]=C.m[i][j];

        }

    }

}

void fast_pow(ll b){

    if(b==0) return;

    D.m[1][1]=1;D.m[1][2]=0;

    D.m[2][1]=0;D.m[2][2]=1;

    D.r=2;D.c=2;

    while(b){

        if(b&1){

            multyply(D,B);

        }

        multyply(B,B);

        b>>=1;

    }

    multyply(A,D);

}

int main(){

    int T;scanf("%d",&T);

    while(T--){

        scanf("%d",&n);

        init();

        if(n==1){

            printf("%d\n",1);

        }

        else if(n==2){

            printf("%d\n",4);

        }

        else{

            if(n-1==2){

                printf("%d\n",6);

            }

            else{

                fast_pow(n-3);

                printf("%I64d\n",3+A.m[1][1]);

            }

        }

    }

    return 0;

}