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

template <class T>
using vc = vector<T>;
template <class T>
using vvc = vector<vc<T>>;
template <class T>
using vvvc = vector<vvc<T>>;
template <class T>
using vvvvc = vector<vvvc<T>>;
template <class T>
using vvvvvc = vector<vvvvc<T>>;

#define vv(type, name, h, w) vector<vector<type>> name(h, vector<type>(w))
#define vvv(type, name, h, w, l) vector<vector<vector<type>>> name(h, vector<vector<type>>(w, vector<type>(l)))
#define vvvv(type, name, a, b, c, d) vector<vector<vector<vector<type>>>> name(a, vector<vector<vector<type>>>(b, vector<vector<type>>(c, vector<type>(d))))
#define vvvvv(type, name, a, b, c, d, e) vector<vector<vector<vector<vector<type>>>>> name(a, vector<vector<vector<vector<type>>>>(b, vector<vector<vector<type>>>(c, vector<vector<type>>(d, vector<type>(e)))))

#define elif else if

#define FOR1(a) for (long long _ = 0; _ < (long long)(a); _++)
#define FOR2(i, n) for (long long i = 0; i < (long long)(n); i++)
#define FOR3(i, l, r) for (long long i = l; i < (long long)(r); i++)
#define FOR4(i, l, r, c) for (long long i = l; i < (long long)(r); i += c)
#define FOR1_R(a) for (long long _ = (long long)(a) - 1; _ >= 0; _--)
#define FOR2_R(i, n) for (long long i = (long long)(n) - 1; i >= (long long)(0); i--)
#define FOR3_R(i, l, r) for (long long i = (long long)(r) - 1; i >= (long long)(l); i--)
#define FOR4_R(i, l, r, c) for (long long i = (long long)(r) - 1; i >= (long long)(l); i -= (c))
#define overload4(a, b, c, d, e, ...) e
#define FOR(...) overload4(__VA_ARGS__, FOR4, FOR3, FOR2, FOR1)(__VA_ARGS__)
#define FOR_R(...) overload4(__VA_ARGS__, FOR4_R, FOR3_R, FOR2_R, FOR1_R)(__VA_ARGS__)
#define FOR_in(a, A) for (auto a: A)
#define FOR_each(a, A) for (auto &&a: A)
#define FOR_subset(t, s) for(long long t = (s); t >= 0; t = (t == 0 ? -1 : (t - 1) & (s)))

#define all(x) x.begin(), x.end()
#define len(x) int(x.size())

int popcount(int x) { return __builtin_popcount(x); }
int popcount(uint32_t x) { return __builtin_popcount(x); }
int popcount(long long x) { return __builtin_popcountll(x); }
int popcount(uint64_t x) { return __builtin_popcountll(x); }
// __builtin_clz(x)は最上位bitからいくつ0があるか.
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(uint32_t x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(long long x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(uint64_t x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }

// 入力
void rd() {}
void rd(char &c) { cin >> c; }
void rd(string &s) { cin >> s; }
void rd(int &x) { cin >> x; }
void rd(uint32_t &x) { cin >> x; }
void rd(long long &x) { cin >> x; }
void rd(uint64_t &x) { cin >> x; }
template<class T>
void rd(vector<T> &v) {
  for (auto& x:v) rd(x);
}

void read() {}
template <class H, class... T>
void read(H &h, T &... t) {
  rd(h), read(t...);
}

#define CHAR(...) \
  char __VA_ARGS__; \
  read(__VA_ARGS__)

#define STRING(...) \
  string __VA_ARGS__; \
  read(__VA_ARGS__)

#define INT(...) \
  int __VA_ARGS__; \
  read(__VA_ARGS__)

#define U32(...) \
  uint32_t __VA_ARGS__; \
  read(__VA_ARGS__)

#define LL(...) \
  long long __VA_ARGS__; \
  read(__VA_ARGS__)

#define U64(...) \
  uint64_t __VA_ARGS__; \
  read(__VA_ARGS__)

#define VC(t, a, n) \
  vector<t> a(n); \
  read(a)

#define VVC(t, a, h, w) \
  vector<vector<t>> a(h, vector<t>(w)); \
  read(a)

//出力
void wt() {}
void wt(const char c) { cout << c; }
void wt(const string s) { cout << s; }
void wt(int x) { cout << x; }
void wt(uint32_t x) { cout << x; }
void wt(long long x) { cout << x; }
void wt(uint64_t x) { cout << x; }
void wt(double x) { cout << fixed << setprecision(16) << x; }
void wt(long double x) { cout << fixed << setprecision(16) << x; }

template<class T>
void wt(const vector<T> v) {
  int n = v.size();
  for (int i = 0; i < n; i++) {
    if (i) wt(' ');
    wt(v[i]);
  }
}

void print() { wt('\n'); }
template <class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
  wt(head);
  if (sizeof...(Tail)) wt(' ');
  print(forward<Tail>(tail)...);
}

/////////////////////////////////////////////////////////////////////////////////////////
long long min(long long a, long long b) { return a < b ? a : b; }

template <class T>
T min(vector<T> A) {
  assert (A.size());
  T S = A[0];
  for (T a : A) S = min(a, S);
  return S;
}

long long max(long long a, long long b) { return a > b ? a : b; }

template <class T>
T max(vector<T> A) {
  assert (A.size());
  T S = A[0];
  for (T a : A) S = max(a, S);
  return S;
}

long long add(long long x, long long y) {return x + y; }

template <class mint>
mint add(mint x, mint y) { return x + y; }

template <class T>
bool chmin(T & x, T a) { return a < x ? (x = a, true) : false; }

template <class T>
bool chmax(T & x, T a) { return a > x ? (x = a, true) : false; }

template <class T>
T sum(vector<T> A) {
  T S = 0;
  for (int i = 0; i < int(A.size()); i++) S += A[i];
  return S;
}

uint64_t random_u64(uint64_t l, uint64_t r) {
  static std::random_device rd;
  static std::mt19937_64 gen(rd());
  std::uniform_int_distribution<uint64_t> dist(l, r);
  return dist(gen);
}

long long gcd(long long a, long long b) {
  while (a) {
    b %= a;
    if (b == 0) return a;
    a %= b;
  }
  return b;
}

long long lcm(long long a, long long b) {
  if (a * b == 0) return 0;
  return a * b / gcd(a, b);
}

long long pow_mod(long long a, long long r, long long mod) {
  long long res = 1, p = a % mod;
  while (r) {
    if ((r % 2) == 1) res = res * p % mod;
    p = p * p % mod, r >>= 1;
  }
  return res;
}

long long mod_inv(long long a, long long mod) {
  if (mod == 1) return 0;
  a %= mod;
  long long b = mod, s = 1, t = 0;
  while (1) {
    if (a == 1) return s;
    t -= (b / a) * s;
    b %= a;
    if (b == 1) return t + mod;
    s -= (a / b) * t;
    a %= b;
  }
}

long long Garner(vector<long long> Rem, vector<long long> Mod, int MOD) {
  assert (Rem.size() == Mod.size());
  long long mod = MOD;
  Rem.push_back(0);
  Mod.push_back(mod);
  long long n = Mod.size();
  vector<long long> coffs(n, 1);
  vector<long long> constants(n, 0);
  for (int i = 0; i < n - 1; i++) {
    long long v = (Mod[i] + Rem[i] - constants[i]) % Mod[i];
    v *= mod_inv(coffs[i], Mod[i]);
    v %= Mod[i];
    for (int j = i + 1; j < n; j++) {
      constants[j] = (constants[j] + coffs[j] * v) % Mod[j];
      coffs[j] = (coffs[j] * Mod[i]) % Mod[j];
    }
  }
  return constants[n - 1];
}

long long Tonelli_Shanks(long long a, long long mod) {
  a %= mod;
  if (a < 2) return a;
  if (pow_mod(a, (mod - 1) / 2, mod) != 1) return -1;
  if (mod % 4 == 3) return pow_mod(a, (mod + 1) / 4, mod);

  long long b = 3;
  if (mod != 998244353) {
    while (pow_mod(b, (mod - 1) / 2, mod) == 1) {
      b = random_u64(2, mod - 1);
    }
  }

  long long q = mod - 1;
  long long Q = 0;
  while (q % 2 == 0) {
    Q++, q /= 2;
  }

  long long x = pow_mod(a, (q + 1) / 2, mod);
  b = pow_mod(b, q, mod);

  long long shift = 2;
  while ((x * x) % mod != a) {
    long long error = (((pow_mod(a, mod - 2, mod) * x) % mod) * x) % mod;
    if (pow_mod(error, 1 << (Q - shift), mod) != 1) {
      x = (x * b) % mod;
    }
    b = (b * b) % mod;
    shift++;
  }
  return x;
}

/////////////////////////////////////////////////////////////////////////////////////////
template <int mod>
struct modint {
  static constexpr uint32_t umod = uint32_t(mod);
  static_assert(umod < (uint32_t(1) << 31));
  uint32_t val;

  static modint raw(uint32_t v) {
    modint x;
    x.val = v % umod;
    return x;
  }

  constexpr modint() : val(0) {}
  constexpr modint(uint32_t x) : val(x % umod) {}
  constexpr modint(uint64_t x) : val(x % umod) {}
  constexpr modint(__uint128_t x) : val(x % umod) {}
  constexpr modint(int x) : val((x %= int(umod)) < 0 ? x + umod : x) {};
  constexpr modint(long long x) : val((x %= int(umod)) < 0 ? x + umod : x) {};
  constexpr modint(__int128_t x) : val((x %= int(umod)) < 0 ? x + umod : x) {};

  bool operator<(const modint &other) const { return val < other.val; }
  modint &operator+=(const modint &p) {
    if ((val += p.val) >= umod) val -= umod;
    return *this;
  }
  modint &operator-=(const modint &p) {
    if ((val += umod - p.val) >= umod) val -= umod;
    return *this;
  }
  modint &operator*=(const modint &p) {
    val = uint64_t(val) * p.val % umod;
    return *this;
  }
  modint &operator/=(const modint &p) {
    val = uint64_t(val) * p.inverse().val % umod;
    return *this;
  }
  modint operator-() const { return modint::raw(val ? umod - val : uint32_t(0)); }
  modint operator+(const modint &p) const { return modint(*this) += p; }
  modint operator-(const modint &p) const { return modint(*this) -= p; }
  modint operator*(const modint &p) const { return modint(*this) *= p; }
  modint operator/(const modint &p) const { return modint(*this) /= p; }
  bool operator==(const modint &p) const { return val == p.val; }
  bool operator!=(const modint &p) const { return val != p.val; }

  modint inverse() const {
    int a = val, b = umod, s = 1, t = 0;
    while (1) {
      if (a == 1) return modint(s);
      t -= (b / a) * s;
      b %= a;
      if (b == 1) return modint(t + umod);
      s -= (a / b) * t;
      a %= b;
    }
  }

  modint pow(long long n) const {
    n %= (long long)(umod);
    if (n < 0) n += umod - 1;
    modint res(1), a(val);
    while (n > 0) {
      if (n & 1) res *= a;
      a *= a;
      n >>= 1;
    }
    return res;
  }

  uint32_t get() const { return val; }

  static constexpr int get_mod() { return mod; }
  
  static constexpr pair<int, int> ntt_info() {
    if (mod == 167772161) return {25, 17};
    if (mod == 469762049) return {26, 30};
    if (mod == 754974721) return {24, 362};
    if (mod == 880803841) return {23, 211};
    if (mod == 998244353) return {23, 31};
    return {-1, -1};
  }
};

template <int mod>
void rd(modint<mod> &x) {
  uint32_t y;
  cin >> y;
  x = y;
}

template <int mod>
void wt(modint<mod> x) {
  wt(x.val);
}

template <typename mint>
mint fact(long long n) {
  static vector<mint> res = {1, 1};
  static long long le = 1;
  if (n < 0) return mint(0);
  while (le <= n){
    le++;
    res.push_back(res[le - 1] * le);
  }
  return res[n];
}

template <typename mint>
mint fact_inv(long long n) {
  static vector<mint> res = {1, 1};
  static long long le = 1;
  if (n < 0) return mint(0);
  while (le <= n) {
    le++;
    res.push_back(res[le - 1] / le);
  }
  return res[n];
}

template <typename mint>
mint binom(long long n, long long r) {
  if (n < 0 || r < 0 || n < r) return 0;
  mint res = fact<mint>(n) * (fact_inv<mint>(n - r) * fact_inv<mint>(r));
  return res;
}

template <class mint>
void ntt(vector<mint> &a, bool inverse) {
  const int mod = mint::get_mod();
  const int rank2 = mint::ntt_info().first;
  static array<mint, 30> root, rate2, rate3, iroot, irate2, irate3;

  static bool prepared = 0;
  if (!prepared) {
    prepared = 1;
    root[rank2] = mint::ntt_info().second;
    iroot[rank2] = mint(1) / root[rank2];
    for (int i = rank2 - 1; i >= 0; i--) {
      root[i] = root[i + 1] * root[i + 1];
      iroot[i] = iroot[i + 1] * iroot[i + 1];
    }

    mint prod = 1, iprod = 1;
    for (int i = 0; i < rank2; i++) {
      rate2[i] = root[i + 2] * prod;
      irate2[i] = iroot[i + 2] * iprod;
      prod *= iroot[i + 2];
      iprod *= root[i + 2];
    }

    prod = 1, iprod = 1;
    for (int i = 0; i < rank2 - 1; i++) {
      rate3[i] = root[i + 3] * prod;
      irate3[i] = iroot[i + 3] * iprod;
      prod *= iroot[i + 3];
      iprod *= root[i + 3];
    }
  }

  int n = int(a.size()), h = (n == 0 ? -1 : 31 - __builtin_clz(n));

  if (!inverse) {
    int le = 0;
    while (le < h) {
      if (h - le == 1) {
        int p = 1 << (h - le - 1);
        mint rot = 1;
        for (int s = 0; s < (1 << le); s++) {
          int offset = s << (h - le);
          for (int i = 0; i < p; i++) {
            auto l = a[i + offset];
            auto r = a[i + offset + p] * rot;
            a[i + offset] = l + r;
            a[i + offset + p] = l - r;
          }
          rot *= rate2[((~s & -~s) == 0 ? -1 : 31 - __builtin_clz(~s & -~s))];
        }
        le++;
      }
      else {
        int p = 1 << (h - le - 2);
        mint rot = 1, imag = root[2];
        for (int s = 0; s < (1 << le); s++) {
          mint rot2 = rot * rot;
          mint rot3 = rot2 * rot;
          int offset = s << (h - le);
          for (int i = 0; i < p; i++) {
            uint64_t mod2 = uint64_t(mod) * mod;
            uint64_t a0 = a[i + offset].get();
            uint64_t a1 = uint64_t(a[i + offset + p].get()) * rot.get();
            uint64_t a2 = uint64_t(a[i + offset + p * 2].get()) * rot2.get();
            uint64_t a3 = uint64_t(a[i + offset + p * 3].get()) * rot3.get();
            uint64_t a1na3imag = (a1 + mod2 - a3) % mod * imag.get();
            a[i + offset] = a0 + a2 + a1 + a3;
            a[i + offset + p] = a0 + a2 + (2 * mod2 - (a1 + a3));
            a[i + offset + p * 2] = a0 + mod2 - a2 + a1na3imag;
            a[i + offset + p * 3] = a0 + mod2 - a2 + (mod2 - a1na3imag);
          }
          rot = rot * rate3[((~s & -~s) == 0 ? -1 : 31 - __builtin_clz(~s & -~s))];
        }
        le = le + 2;
      }
    }
  }
  else {
    mint coef = mint(n).inverse();
    for (int i = 0; i < n; i++) {
      a[i] *= coef;
    }
    int le = h;
    while (le) {
      if (le == 1) {
        int p = 1 << (h - le);
        mint irot = 1;
        for (int s = 0; s < (1 << (le - 1)); s++) {
          int offset = s << (h - le + 1);
          for (int i = 0; i < p; i++) {
            uint64_t l = a[i + offset].get();
            uint64_t r = a[i + offset + p].get();
            a[i + offset] = l + r;
            a[i + offset + p] = (mod + l - r) * irot.get();
          }
          irot *= irate2[((~s & -~s) == 0 ? -1 : 31 - __builtin_clz(~s & -~s))];
          }
        le--;
      }
      else {
        int p = 1 << (h - le);
        mint irot = 1, iimag = iroot[2];
        for (int s = 0; s < (1 << (le - 2)); s++) {
          mint irot2 = irot * irot;
          mint irot3 = irot2 * irot;
          int offset = s << (h - le + 2);
          for (int i = 0; i < p; i++) {
            uint64_t a0 = a[i + offset].get();
            uint64_t a1 = a[i + offset + p].get();
            uint64_t a2 = a[i + offset + p * 2].get();
            uint64_t a3 = a[i + offset + p * 3].get();
            uint64_t a2na3iimag = (mod + a2 - a3) * iimag.get() % mod;
            a[i + offset] = a0 + a1 + a2 + a3;
            a[i + offset + p] = (a0 + mod - a1 + a2na3iimag) * irot.get();
            a[i + offset + p * 2] = (a0 + a1 + 2 * mod - a2 - a3) * irot2.get();
            a[i + offset + p * 3] = (a0 + 2 * mod - a1 - a2na3iimag) * irot3.get();
          }
          irot *= irate3[((~s & -~s) == 0 ? -1 : 31 - __builtin_clz(~s & -~s))];
        }
        le = le - 2;
      }
    }
  }
}

template <class mint>
vector<mint> convolution_naive(vector<mint> a, vector<mint> b) {
  vector<mint> res(size(a) + size(b) - 1);
  for (int i = 0; i < int(size(a)); i++) {
    if (a[i] == mint(0)) continue; 
    for (int j = 0; j < int(size(b)); j++) {
      res[i + j] = res[i + j] + a[i] * b[j];
    }
  }
  return res;
}

template <class mint>
vector<mint> convolution_ntt(vector<mint> a, vector<mint> b) {
  int n = a.size();
  int m = b.size();
  if (min(n, m) <= 60) return convolution_naive(a, b);
  int le = 1;
  while (le < n + m - 1) le = le * 2;
  a.resize(le), b.resize(le);
  ntt(a, 0), ntt(b, 0);
  for (int i = 0; i < le; i++) a[i] *= b[i];
  ntt(a, 1);
  a.resize(n + m - 1);
  return a;
}

template <class mint>
vector<mint> convolution_garner(vector<mint> a, vector<mint> b) {
  const int mod = mint::get_mod();
  int n = int(a.size()), m = int(b.size());
  if (min(n, m) <= 60) return convolution_naive(a, b);
  const vector<long long> nttfriend = {167772161, 469762049, 754974721};
  using mint1 = modint<167772161>;
  using mint2 = modint<469762049>;
  using mint3 = modint<754974721>;
  vector<mint1> a1(n), b1(m);
  vector<mint2> a2(n), b2(m);
  vector<mint3> a3(n), b3(m);
  for (int i = 0; i < n; i++) {
    a1[i] = a[i].get(), a2[i] = a[i].get(), a3[i] = a[i].get();
  }
  for (int i = 0; i < m; i++) {
    b1[i] = b[i].get(), b2[i] = b[i].get(), b3[i] = b[i].get();
  }
  vector<mint1> c1 = convolution_ntt(a1, b1);
  vector<mint2> c2 = convolution_ntt(a2, b2);
  vector<mint3> c3 = convolution_ntt(a3, b3);

  vector<mint> c(n + m - 1);
  for (int i = 0; i < n + m - 1; i++) {
    vector<long long> Rem = {c1[i].get(), c2[i].get(), c3[i].get()};
    c[i] = mint(Garner(Rem, nttfriend, mod));
  }
  return c;
}

template <class mint>
vector<mint> convolution(vector<mint> a, vector<mint> b) {
  if (mint::ntt_info().first == -1) return convolution_garner(a, b);
  return convolution_ntt(a, b);
}

using mint = modint<998244353>;

mint C(int n) {
  return binom<mint>(2 * n, n) - binom<mint>(2 * n, n - 1);
}

// 前と微妙に違う
int main() {
  vector<mint> f, g;
  int N = 1000000;
  f.resize(N + 1, mint(0)), g.resize(N + 1, mint(0));
  FOR(i, 2, N + 1, 2) f[i] = mint(i - 1) * C((i - 2) / 2), g[i] = mint(i + 1) * C(i / 2);
  g[0] = mint(1);
  f = convolution(f, g);
  INT(T);
  FOR(T) {
    INT(n);
    print(f[n - 2]);
  }
}