#include <bits/stdc++.h>
using namespace std ;
const int mod = 998244353 ;
int norm(int x)
{
	if(x < 0)  x += mod ;
	if(x >= mod)  x -= mod ;
	return x ;
}
template<class T>
T power(T a , int b)
{
	T res = 1 ;
	for( ; b ; b /= 2 , a *= a)
	if(b % 2)  res *= a ;
	return res ;
}
template<class T>
T print(T a , int b)
{
	T res = 1 ;
	for( ; b ; b /= 2 , a *= a)
	if(b % 2)  res *= a ;
	return res ;
}
struct mint
{
	int x ;
	mint(int x = 0) : x(norm(x)) {}
	int val() const
	{
		return x ;
	}
	mint operator-() const
	{
		return mint(norm(mod - x)) ;
	}
	mint inv() const
	{
		assert(x != 0);
		return power(*this, mod - 2) ;
	}
	mint &operator*=(const mint &rhs)
	{
		x = (long long)x * rhs.x % mod ;
		return *this ;
	}
	mint &operator+=(const mint &rhs)
	{
		x = norm(x + rhs.x) ;
		return *this ;
	}
	mint &operator-=(const mint &rhs)
	{
		x = norm(x - rhs.x) ;
		return *this ;
	}
	mint &operator/=(const mint &rhs)
	{
		return *this *= rhs.inv() ;
	}
	friend mint operator*(const mint &lhs , const mint &rhs)
	{
		mint res = lhs ;
		res *= rhs ;
		return res ;
	}
	friend mint operator+(const mint &lhs , const mint &rhs)
	{
		mint res = lhs ;
		res += rhs ;
		return res ;
	}
	friend mint operator-(const mint &lhs , const mint &rhs)
	{
		mint res = lhs ;
		res -= rhs ;
		return res ;
	}
	friend mint operator/(const mint &lhs , const mint &rhs)
	{
		mint res = lhs ;
		res /= rhs ;
		return res ;
	}
} ;
ostream& operator<<(std::ostream& os, const mint& m) 
{
	os << m.x ;
	return os ;
}
vector<mint> fac ;
vector<mint> inv ;
void init(int n)
{
	n <<= 1 ;
	fac.resize(0) ;
	fac.resize(n + 10 , mint(1)) ;
	inv.resize(0) ;
	inv.resize(n + 10 , mint(1)) ;
	for(int i = 2 ; i <= n ; i ++)  fac[i] = fac[i - 1] * i ;
	inv[n] = fac[n].inv() ;
	for(int i = n - 1 ; i >= 1 ; i --)  inv[i] = inv[i + 1] * (i + 1) ;
}
mint C(int n , int m)
{
	if(n < 0 || m < 0 || n < m)  return mint(0) ;
	return fac[n] * inv[m] * inv[n - m] ;
}

template<typename T>
struct Matrix
{
	int n ;
	vector<vector<T>> a ;
	Matrix() {}
	Matrix(int t)
	{
		n = t ;
		a.resize(0) ;
		a.resize(n , vector<T>(n , T())) ;
	}
	void norm()
	{
		a.resize(0) ;
		a.resize(n , vector<T>(n , T())) ;
		for(int i = 0 ; i < n ; i ++)  a[i][i] = 1 ;
	}
	void print()
	{
		for(int i = 0 ; i < n ; i ++)
		for(int j = 0 ; j < n ; j ++)
		cout << a[i][j] << " \n"[j == n - 1] ;
	}
	Matrix operator *(Matrix m2)
	{
		assert(n == m2.n) ;
		Matrix res(n) ;
		for(int i = 0 ; i < n ; i ++)
		for(int j = 0 ; j < n ; j ++)
		for(int k = 0 ; k < n ; k ++)
		{
			res.a[i][j] += a[i][k] * m2.a[k][j] ;
		}
		return res ;
	}
	Matrix qpow(Matrix c , int d)
	{
		Matrix res(n) ;
		res.norm() ;
		Matrix base = c ;
		while(d > 0)
		{
			if(d & 1)  res = res * base ;
			base = base * base ;
			d >>= 1 ;
		}
		return res ;
	}
} ;

vector<Matrix<mint>> v[20];
int base=50;

void solve()
{
    /*


    dp[i + 1][j][k] += 50 * dp[i][j][k]
    dp[i + 1][j + 1][k] += dp[i][j][k]
    dp[i + 1][j][k + 1] += dp[i][j][k]
    
    i = 1e9
    j < 5
    k < 5
    \sum dp[i][j][k]

    */

    int n ;
    cin >> n ;
    Matrix<mint> a(49);
    a.a[0][0] = 1 ;
    for(int i=0;i<=10;i++){
        int t=n%base;
        // cout<<t<<endl;
        if(t==0) continue;
        a=a*v[i][t];
        n/=base;
    }
    cout << a.a[0][48] << '\n' ;
}
int main()
{
    
    std::ios::sync_with_stdio(false) , cin.tie(0) ;
    Matrix<mint> a(49),aa(49) ;
    a.a[0][0] = 1 ;
    aa=a;
    Matrix<mint> b(49) ;

    for(int i = 0 ; i < 49 ; i ++)  b.a[i][i] += 50 ;
    
    auto id = [&](int x , int y)
    {
        return x * 7 + y ;
    } ;

    for(int i = 0 ; i < 49 ; i ++)
    {
        int x = i / 7 ;
        int y = i % 7 ;
        if(x + 1 < 7)  b.a[i][id(x + 1 , y)] += 1 ;
        else  b.a[i][i] += 1 ;
        if(y + 1 < 7)  b.a[i][id(x , y + 1)] += 1 ;
        else  b.a[i][i] += 1 ;
    }
    for(int i=0;i<=10;i++){
        v[i].push_back(aa);
        if(i==0) v[i].push_back(b);
        else v[i].push_back(v[i-1].back());
        // for(int j=2;j<=base;) v[i].push_back(aa);
        for(int j=2;j<=base;j++){
            Matrix<mint> vvv=v[i][j-1]*v[i][1];
            v[i].push_back(vvv);
        }
    }

    int T = 1 ;
    cin >> T ;
    while (T --)  solve() ;

    return 0 ;
}