#include #include using namespace std; using ll = long long; #define rep(i, s, t) for (ll i = s; i < (ll)(t); i++) #define all(x) begin(x), end(x) template bool chmin(T& x, T y) { return x > y ? (x = y, true) : false; } template bool chmax(T& x, T y) { return x < y ? (x = y, true) : false; } struct io_setup { io_setup() { ios::sync_with_stdio(false); cin.tie(nullptr); cout << fixed << setprecision(15); } } io_setup; namespace cho { using namespace std; template struct matrix { int h, w; std::vector> d; matrix() { } matrix(int _h, int _w, T val = 0) : h(_h), w(_w), d(_h, vector(_w, val)) { } matrix(vector> const& dat) : h(dat.size()), w(0), d(dat) { if (h > 0) w = d[0].size(); } static matrix unit(int n) { matrix uni(n, n, 0); for (int i = 0; i < n; i++) uni[i][i] = 1; return uni; } const vector& operator[](int i) const { return d[i]; } vector& operator[](int i) { return d[i]; } matrix& operator*=(const matrix& a) { return *this = (*this) * a; } matrix operator*(const matrix& a) const { assert(w == a.h); matrix r(h, a.w); for (int i = 0; i < h; i++) for (int k = 0; k < w; k++) for (int j = 0; j < a.w; j++) { r[i][j] += d[i][k] * a[k][j]; } return r; } matrix pow(long long t) const { assert(h == w); matrix res = matrix::unit(h); matrix x = (*this); while (t > 0) { if (t & 1) res = res * x; x = x * x; t >>= 1; } return res; } }; } // namespace cho using mint = atcoder::modint998244353; cho::matrix one7(7, 7); void solve() { ll n; cin >> n; mint ans = 0; ans += one7.pow(n)[0][0]; ans -= mint(2).pow(n - 1); cout << ans.val() << "\n"; cout << flush; } int main() { rep(i, 0, 2) { rep(j, 0, 2) { one7[i * 2 + j][i * 2 + j] = 1; one7[i * 2 + j][i * 2 + 1 - j] = 1; one7[i * 2 + j][(i + 1) * 2 + j] = 1; one7[i * 2 + j][(i + 1) * 2 + 1 - j] = 1; } } { one7[4][4] = 1; one7[4][5] = 1; one7[4][0] = 1; one7[4][6] = 1; } { one7[5][4] = 1; one7[5][5] = 1; one7[5][0] = 1; one7[5][6] = 1; } { one7[6][6] = 1; one7[6][0] = 1; } int t = 1; cin >> t; while (t--) solve(); }