#include long long int modpow(long long int a, long long int n, long long int p) { long long int res = 1; for (; n > 0; n /= 2, a = a * a % p) if (n % 2 > 0) res = res * a % p; return res; } void chmul(long long int a[7][7], long long int b[7][7], long long int p) { long long int c[7][7]; long long int i, j, k; for (i = 0; i < 7; i++) for (j = 0; j < 7; j++) c[i][j] = 0; for (i = 0; i < 7; i++) for (j = 0; j < 7; j++) for (k = 0; k < 7; k++) c[i][j] += a[i][k] * b[k][j] % p; for (i = 0; i < 7; i++) for (j = 0; j < 7; j++) a[i][j] = c[i][j] % p; return; } void solve() { long long int n; scanf("%lld", &n); long long int A[7][7] = { {1,1,0,0,1,1,1}, {1,1,0,0,0,0,0}, {1,1,1,1,0,0,0}, {1,1,1,1,0,0,0}, {0,0,1,1,1,1,0}, {0,0,1,1,1,1,0}, {0,0,0,0,1,1,1} }; long long int res[7][7] = { {1,0,0,0,0,0,0}, {0,1,0,0,0,0,0}, {0,0,1,0,0,0,0}, {0,0,0,1,0,0,0}, {0,0,0,0,1,0,0}, {0,0,0,0,0,1,0}, {0,0,0,0,0,0,1} }; const long long int p = 998244353; long long int ans = p - modpow(2, n - 1, p); for (; n > 0; n /= 2, chmul(A, A, p)) if (n % 2 > 0) chmul(res, A, p); ans = (ans + res[0][0]) % p; printf("%lld\n", ans); return; } int main() { int t; scanf("%d", &t); for (; t > 0; t--) solve(); return 0; }