#include #include #include using namespace std; std::vector> mul(const std::vector> &v1, const std::vector> &v2, long long mod = 998244353) { std::vector> ans; if (v1.size() != v2[0].size()) return ans; ans.assign(v1.size(), std::vector (v2[0].size(), 0)); for (int i = 0; i < v1.size(); ++i) for (int j = 0; j < v2[0].size(); ++j) for (int k = 0; k < v2.size(); ++k) ans[i][j] = (ans[i][j] + v1[i][k] * v2[k][j]) % mod; return ans; } std::vector> pow(std::vector> v, long long k, long long mod = 998244353) { std::vector> ans; if (v.size() != v[0].size()) return ans; ans.assign(v.size(), std::vector (v.size(), 0)); for (int i = 0; i < v.size(); ++i) ans[i][i] = 1; for (; k > 0; k >>= 1, v = mul(v, v, mod)) if (k & 1) ans = mul(v, ans, mod); return ans; } int main() { const int mod = 998244353; int t; cin >> t; const int siz = 9; vector> bs(siz, vector (siz)); int val[siz] = {1, -1, 2, -2, 4, -4, 8, -8, 0}; int c[4] = {1, -1, 2, -2}; for (int i = 0; i < siz; ++i) { if (val[i] == 8) { ++bs[siz - 3][i]; ++bs[siz - 1][i]; ++bs[2][i]; ++bs[3][i]; } else if (val[i] == 0) { ++bs[siz - 1][i]; ++bs[siz - 3][i]; ++bs[2][i]; ++bs[3][i]; } else { for (int j = 0; j < 4; ++j) { int tmp = val[i] * c[j]; if (abs(tmp) > 8) { if (val[i] == 8) tmp = c[j]; else continue; } for (int k = 0; k < siz; ++k) { if (val[k] == tmp) { ++bs[k][i]; } } } } } while (t--) { long long n; cin >> n; auto mat = bs; auto res = pow(mat, n, mod); long long ans = (res[siz - 3][0]) % mod; cout << ans << endl; } }