#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const long long MOD=1000000007;
vector<int> graph[12];
unsigned long long a[100001][11];
int main()
{
	int t,k,i,j,n,m,b,c,d,e,f;
	graph[0].push_back(7);

	graph[1].push_back(2);
	graph[1].push_back(4);

	graph[2].push_back(1);
	graph[2].push_back(3);
	graph[2].push_back(5);

	graph[3].push_back(2);
	graph[3].push_back(6);

	graph[4].push_back(1);
	graph[4].push_back(5);
	graph[4].push_back(7);

	graph[5].push_back(2);
	graph[5].push_back(4);
	graph[5].push_back(6);
	graph[5].push_back(8);

	graph[6].push_back(3);
	graph[6].push_back(5);
	graph[6].push_back(9);
	
	graph[7].push_back(4);
	graph[7].push_back(8);
	graph[7].push_back(0);

	graph[8].push_back(7);
	graph[8].push_back(5);
	graph[8].push_back(9);

	graph[9].push_back(6);
	graph[9].push_back(8);
	for(i=0;i<=9;i++)
		a[1][i]=1;
	a[1][10]=10;
	for(i=2;i<=100000;i++)
	{
		for(j=0;j<=9;j++)
		{
			for(k=0;k<graph[j].size();k++)
			{
				a[i][graph[j][k]]+=a[i-1][j];
			}
		}
		for(j=0;j<=9;j++)
			a[i][j]=a[i][j]%MOD;
		for(j=0;j<=9;j++)
			a[i][10]=a[i][10]+a[i][j];
		a[i][10]=a[i][10]%MOD;
	}
	scanf("%d",&t);
	for(k=1;k<=t;k++)
	{
		scanf("%d",&n);
		printf("%d\n",a[n][10]);
	}	
	return 0;
}