#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

const int MOD=1e9+;

int dp[][];

//dp[i][j] 表示长度为i结尾字符为j的合法字符有多少种

void init()

{

    memset(dp,,sizeof(dp));

    for(int i=; i<; i++) //前三位都是合法字符，初始化数值

    {

        dp[][i]=;

        dp[][i]=;

        dp[][i]=;

    }

    for(int i=; i<=; i++)

    {

        for(int j=; j<; j++)          //连续三个字符相等的

            for(int k=; k<; k++)

            {

                if(k==j) continue;

                dp[i][j]=(dp[i][j]+dp[i-][k])%MOD;

            }

        for(int j=; j<; j++)          //连续两个字符相等的

            for(int k=; k<; k++)

            {

                if(k==j) continue;

                dp[i][j]=(dp[i][j]+dp[i-][k])%MOD;

            }

        for(int j=; j<; j++)          //连续一个字符相等的

            for(int k=; k<; k++)

            {

                if(k==j) continue;

                dp[i][j]=(dp[i][j]+dp[i-][k])%MOD;

            }

    }

}

int main()

{

    init();

    int T,n;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&n);

        int ans=;

        for(int i=; i<; i++)

            ans=(ans+dp[n][i])%MOD;

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

    }

    return ;

}