//code_board
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef double db;
typedef pair<int,int> pa;
typedef vector<int> vec;
typedef string str;

const int bias = 5;
const int MOD = 998244353;

#define endl '\n'

int T;

class Matrix {
public:
    int rows, cols;
    // vector<vector<ll>> mat;
    int mat[49][49];

    Matrix(int r, int c) : rows(r), cols(c) {
        // mat.resize(r, vector<ll>(c, 0));
        memset(mat, 0, sizeof(mat));
    }

    Matrix operator*(const Matrix& other) const {
        Matrix result(rows, other.cols);
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < other.cols; ++j) {
                for (int k = 0; k <= i; ++k) {
                    (result.mat[i][j] += 1ll * mat[i][k] * other.mat[k][j] % MOD) %= MOD;
                }
            }
        }
        return result;
    }

    Matrix operator-(const Matrix& other) const {
        Matrix result(rows, other.cols);
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j <= i; ++j) {
                for (int k = j; k <= i; ++k) {
                    (result.mat[i][j] += 1ll * mat[i][k] * other.mat[k][j] % MOD) %= MOD;
                }
            }
        }
        return result;
    }

    Matrix pow(ll exp) const {
        Matrix result(rows, cols);
        Matrix base = *this;

        // Initialize result as identity matrix
        for (int i = 0; i < rows; ++i) {
            result.mat[i][i] = 1;
        }

        while (exp > 0) {
            if (exp & 1) {
                result = result * base;
            }
            base = base * base;
            exp >>= 1;
        }

        return result;
    }

    void print() const {
        for (int i = 0; i < rows; ++i) {
            for (int j = 0; j < cols; ++j) {
                cout << mat[i][j] << " ";
            }
            cout << endl;
        }
    }
}EX(49, 49);

vector<Matrix> EXs;

int num(int a, int b) {
    return a * 7 + b;
}

void init() {
    for (int a = 0; a <= 6; a++) {
        for (int b = 0; b <= 6; b++) {
            int k = num(a, b);
            if(a){
                int t = num(a - 1, b);
                EX.mat[k][t] = 1;
            }
            if(b){
                int t = num(a, b - 1);
                EX.mat[k][t] = 1;
            }
            EX.mat[k][k] = 26 + 26 - (a != 6) - (b != 6);
        }
    }
    // EX.print();
    for(int i = 0; i < 33; i++){
        // EX.print();
        EXs.push_back(EX);
        EX = EX - EX;
    }
}

map<int, int> mans;

void solve() {
    int n;
    cin >> n;
    if(mans.contains(n))
    {
        cout << n << '\n';
        return;
    }
    Matrix ans(49, 1), adj(49, 49);
    ans.mat[0][0] = 1;
    int cnt = 0;
    for(int i = 0; i < 49; i++){
        adj.mat[i][i] = 1;
    }
    int nn = n;
    while(n){
        if(n & 1){
            adj = adj - EXs[cnt];
        }
        cnt++;
        n >>= 1;
    }
    ans = adj * ans;
    // ans.print();
    cout << ans.mat[num(6, 6)][0] << '\n';
    mans[nn] = ans.mat[num(6, 6)][0];
}

int main() {
    // 示例代码
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    init();
    cin >> T;
    while(T--) solve();
    return 0;
}