#include<bits/stdc++.h>
using namespace std;
int read(){
	int s = 0, f = 1;char ch = getchar();
	while(!isdigit(ch)){if(ch == '-')f = -1;ch = getchar();}
	while(isdigit(ch)){s = s * 10 + ch - '0';ch = getchar();}
	return s * f;
}
void write(int x){
    if(x < 0){putchar('-'); x = -x;}
    if(x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
const int MOD = 998244353;
int t, n, m;
struct Matrix{
	int c[50][50];
	Matrix operator * (const Matrix &zzz)const{
		Matrix tmp;
		memset(tmp.c, 0, sizeof(tmp.c));
		for(int i = 0;i < 49;i ++){
			for(int k = 0;k < 49;k ++){
				for(int j = 0;j < 49;j ++)
					tmp.c[i][j] = (tmp.c[i][j] + c[i][k] * zzz.c[k][j] % MOD) % MOD;
			}
		}
		return tmp;
	}
}c[50];
int g(int x, int y){
	return x * 7 + y;
}
int main(){
	for(int i = 1;i < 7;i ++){
		for(int j = 1;j < 7;j ++)
			c[0].c[g(i, j)][g(i, j)] = 50, c[0].c[g(i, j - 1)][g(i, j)] = c[0].c[g(i - 1, j)][g(i, j)] = 1;
	}
	for(int i = 1;i < 7;i ++)c[0].c[g(i - 1, 0)][g(i, 0)] = 1, c[0].c[g(i, 0)][g(i, 0)] = 51;
	for(int i = 1;i < 7;i ++)c[0].c[g(i - 1, 0)][g(0, i)] = 1, c[0].c[g(i, 0)][g(0, i)] = 51;
	c[0].c[0][0] = 50;//总-2 
	c[0].c[48][48] = 52;
	for(int i = 1;i <= 31;i ++)c[i] = c[i - 1] * c[i - 1];
	int t = read();
	while(t --){
		int n = read();
		if(n < 12){
			puts("0");
			continue;
		}
		Matrix g;
		memset(g.c, 0, sizeof(g.c));
		g.c[0][0] = 1;
		for(int i = 31;i >= 0;i --){
			if(n >= (1ll << i))g = g * c[i], n -= (1ll << i);
		}
		printf("%lld\n", g.c[0][48]);
	}
	return 0;
}