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

#include <atcoder/all>
using namespace atcoder;

using ll = long long;
using mint = modint998244353;

using MAT = vector<vector<mint>>;

MAT matprod(MAT A, MAT B) {
    int H = A.size();
    int W = B[0].size();
    int K = A[0].size();
    MAT C(H, vector<mint>(W));
    for(int i = 0; i < H; i++) {
        for(int j = 0; j < W; j++) {
            for(int k = 0; k < K; k++) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}

MAT matpow(MAT A, ll n) {
    int N = A.size();
    MAT C(N, vector<mint>(N));
    for(int i = 0; i < N; i++) C[i][i] = 1;
    while(n) {
        if(n & 1) C = matprod(C, A);
        A = matprod(A, A);
        n /= 2;
    }
    return C;
}

void solve() {
    MAT coef = {
        {1, 0, 1, 1, 0, 1, 1},
        {1, 1, 0, 1, 1, 0, 0},
        {0, 1, 1, 0, 1, 1, 0},
        {1, 0, 0, 1, 0, 0, 0},
        {1, 1, 0, 1, 1, 0, 0},
        {0, 1, 1, 0, 1, 1, 0},
        {0, 0, 1, 0, 0, 1, 1}
    };
    MAT fi = {
        {1},
        {0},
        {0},
        {0},
        {0},
        {0},
        {0}
    };
    ll n;
    cin >> n;
    MAT dp = matprod(matpow(coef, n), fi);
    // for(int i = 0; i < 7; i++) cout << dp[i][0].val() << " \n"[i == 6];
    cout << (dp[0][0] - mint(2).pow(n - 1)).val() << endl;
}

int main() {
    int t;
    cin >> t;
    while(t--) solve();
}