#include namespace { #pragma GCC diagnostic ignored "-Wunused-function" #include #pragma GCC diagnostic warning "-Wunused-function" using namespace std; using namespace atcoder; #define rep(i,n) for(int i = 0; i < (int)(n); i++) #define rrep(i,n) for(int i = (int)(n) - 1; i >= 0; i--) #define all(x) begin(x), end(x) #define rall(x) rbegin(x), rend(x) template bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; } template bool chmin(T& a, const T& b) { if (b < a) { a = b; return true; } else return false; } using ll = long long; using P = pair; using VI = vector; using VVI = vector; using VL = vector; using VVL = vector; using mint = modint998244353; template struct Mat : array, N> { using M = Mat; void make_identity() { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { (*this)[i][j] = zero(); } } for (int i = 0; i < N; i++) { (*this)[i][i] = one(); } } M& operator+=(const M& rhs) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { (*this)[i][j] = add((*this)[i][j], rhs[i][j]); } } return *this; } M& operator*=(const M& rhs) { static M temp; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { temp[i][j] = zero(); } } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { for (int k = 0; k < N; k++) { temp[i][k] = add(temp[i][k], mul((*this)[i][j], rhs[j][k])); } } } *this = temp; return *this; } template void inplace_pow(I k) { assert(k >= 0); static M temp; temp = *this; make_identity(); while (k) { if (k & 1) *this *= temp; k >>= 1; if (k) temp *= temp; } } friend ostream& operator<<(ostream& os, const M& A) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { os << A[i][j] << " \n"[j + 1 == N]; } } return os; } }; mint add(mint x, mint y) { return x + y; } mint zero() { return mint(); } mint mul(mint x, mint y) { return x * y; } mint one() { return mint::raw(1); } using M = Mat; } int main() { ios::sync_with_stdio(false); cin.tie(0); M memo[60]; { M a; int v[]{1, 2, 4, -1, -2, -4, -8}; rep(i, 7) { for (int x : {v[i], v[i] * -1, v[i] * 2, v[i] * -2}) { if (x == 8) a[i][0]++; else if (int j = find(all(v), x) - v; j != 7) a[i][j]++; } } memo[0] = a; } rep(i, 59) { memo[i+1] = memo[i]; memo[i+1] *= memo[i]; } int tt; cin >> tt; while (tt--) { ll n; cin >> n; mint v[7]; v[0] = 1; rep(k, 60) if (n >> k & 1) { mint nv[7]; rep(i, 7) rep(j, 7) nv[j] += v[i] * memo[k][i][j]; swap(v, nv); } mint ans = v[0] - mint(2).pow(n - 1); cout << ans.val() << '\n'; } }