#include <bits/stdc++.h>
using namespace std;

const int Mod=998244353;

struct Matrix
{
	long long a[50][50];

	Matrix()
	{
		memset(a,0,sizeof(a));
	}

	Matrix operator *(const Matrix& oth) const
	{
		Matrix res;
		for(int i=0;i<=6;i++)
			for(int j=0;j<=6;j++)
			{
				int S=i*7+j;
				for(int k=i;k<=6;k++)
					for(int p=j;p<=6;p++)
					{
						int T=k*7+p;
						if(a[S][T])
						{
							for(int x=k;x<=6;x++)
								for(int y=p;y<=6;y++)
								{
									int r=x*7+y;
									(res.a[S][r] += a[S][T]*oth.a[T][r]) %= Mod;
								}
						}
					}
			}
		
		return res;
	}
} trans[35];

map <int,int> ans;

void work()
{
	int n;
	scanf("%d",&n);
	if(ans.count(n))
		printf("%d\n",ans[n]);

	Matrix start;
	start.a[0][0]=1;
	for(int i=0;i<=30;i++)
		if((n>>i)&1)
			start=start*trans[i];
	ans[n]=start.a[0][48];
	printf("%d\n",ans[n]);
}

int main()
{
	for(int i=0;i<=6;i++)
		for(int j=0;j<=6;j++)
		{
			int sum=52;
			if(i!=6)
				trans[0].a[i*7+j][(i+1)*7+j]++, sum--;

			if(j!=6)
				trans[0].a[i*7+j][i*7+j+1]++, sum--;

			trans[0].a[i*7+j][i*7+j]=sum;
		}

	for(int i=1;i<=30;i++)
		trans[i]=trans[i-1]*trans[i-1];

	int T;
	cin >> T;
	while(T--)
		work();
	return 0;
}