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

const int N = 3e5 + 9, mod = 998244353;

template <const int32_t MOD>
struct modint {
    int32_t value;
    modint() = default;
    modint(int32_t value_) : value(value_) {}
    inline modint<MOD> operator + (modint<MOD> other) const { int32_t c = this->value + other.value; return modint<MOD>(c >= MOD ? c - MOD : c); }
    inline modint<MOD> operator - (modint<MOD> other) const { int32_t c = this->value - other.value; return modint<MOD>(c <    0 ? c + MOD : c); }
    inline modint<MOD> operator * (modint<MOD> other) const { int32_t c = (int64_t)this->value * other.value % MOD; return modint<MOD>(c < 0 ? c + MOD : c); }
    inline modint<MOD> & operator += (modint<MOD> other) { this->value += other.value; if (this->value >= MOD) this->value -= MOD; return *this; }
    inline modint<MOD> & operator -= (modint<MOD> other) { this->value -= other.value; if (this->value <    0) this->value += MOD; return *this; }
    inline modint<MOD> & operator *= (modint<MOD> other) { this->value = (int64_t)this->value * other.value % MOD; if (this->value < 0) this->value += MOD; return *this; }
    inline modint<MOD> operator - () const { return modint<MOD>(this->value ? MOD - this->value : 0); }
    modint<MOD> pow(uint64_t k) const {
        modint<MOD> x = *this, y = 1;
        for (; k; k >>= 1) {
            if (k & 1) y *= x;
            x *= x;
        }
        return y;
    }
    modint<MOD> inv() const { return pow(MOD - 2); }  // MOD must be a prime
    inline modint<MOD> operator /  (modint<MOD> other) const { return *this *  other.inv(); }
    inline modint<MOD> operator /= (modint<MOD> other)       { return *this *= other.inv(); }
    inline bool operator == (modint<MOD> other) const { return value == other.value; }
    inline bool operator != (modint<MOD> other) const { return value != other.value; }
    inline bool operator < (modint<MOD> other) const { return value < other.value; }
    inline bool operator > (modint<MOD> other) const { return value > other.value; }
};
template <int32_t MOD> modint<MOD> operator * (int64_t value, modint<MOD> n) { return modint<MOD>(value) * n; }
template <int32_t MOD> modint<MOD> operator * (int32_t value, modint<MOD> n) { return modint<MOD>(value % MOD) * n; }
template <int32_t MOD> istream & operator >> (istream & in, modint<MOD> &n) { return in >> n.value; }
template <int32_t MOD> ostream & operator << (ostream & out, modint<MOD> n) { return out << n.value; }

using mint = modint<mod>;

vector<mint> fact, finv;
// p = first at least n + 1 points of the n degree polynomial, returns f(x)
// O(n)
mint Lagrange(const vector<mint> &p, mint x) {
    int n = p.size() - 1;
    if (x.value <= n) return p[x.value];

    vector<mint> pref(n + 1, 1), suf(n + 1, 1);
    for (int i = 0; i < n; i++) pref[i + 1] = pref[i] * (x - i);
    for (int i = n; i > 0; i--) suf[i - 1] = suf[i] * (x - i);

    mint ans = 0;
    for (int i = 0; i <= n; i++) {
        mint tmp = p[i] * pref[i] * suf[i] * finv[i] * finv[n-i];
        if ((n - i) & 1) ans -= tmp;
        else ans += tmp;
    }

    return ans;
}

const int M = 6;
vector<mint> P[30];
mint ppw2[30];
int pw2[30];

int32_t main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	// precomputing factorials
    fact = finv = vector<mint> (1 << M, 1);
    for (int i = 1; i < (1 << M); i++) fact[i] = fact[i - 1] * i;
    finv[(1 << M) - 1] /= fact[(1 << M) - 1];
    for (int i = (1 << M) - 1; i >= 1; i--) finv[i - 1] = finv[i] * i;

	pw2[0] = 1;
	for (int i = 1; i < 30; i++) pw2[i] = pw2[i - 1] * 2; // 2^i
	for (int i = 0; i < 30; i++) ppw2[i] = mint(pw2[i] % mod).pow(pw2[i]);// (2^i)^(2^i)

	// precomputing first (2^k+1) terms for Lagrange
	for (int k = 0; k < M; k++) {
		mint ans = 0;
		for (int i = 0; i <= (1 << k) + 1; i++) {
			ans += mint(1 + 2 * i).pow(pw2[k]);
			P[k].push_back(ans);
		}
	}

	// precomputing first 2^30/(2^(k+1)) terms
	for (int i = 0; i <= (1 << (30 - M - 1)); i++) {
		mint nw = mint(1 + 2 * i).pow(pw2[M]); // (1 + 2 * i) ^ (2^k)
		P[M].push_back(nw);
	}
	for (int k = M + 1; k < 30; k++) {
		for (int i = 0; i <= (1 << (30 - k - 1)); i++) {
			auto nw = P[k - 1][i] * P[k - 1][i]; // saving extra log (mod) factor
			P[k].push_back(nw);
		}
	}
	for (int k = M; k < 30; k++) {
		for (int i = 1; i <= (1 << (30 - k - 1)); i++) {
			P[k][i] += P[k][i - 1]; // summing up all (1 + 2 * i) ^ (2^k)
		}
	}

	int q; cin >> q;
	while (q--) {
		int n; cin >> n;
		mint ans = 0;
		for (int k = 0; k < 30 && n >= pw2[k]; k++) {
			if (k < M) {
				ans += ppw2[k] * Lagrange(P[k], ((n - pw2[k]) >> (k + 1)) % mod); // use Lagrange for smaller degrees
			}
			else {
				ans += ppw2[k] * P[k][(n - pw2[k]) >> (k + 1)]; // use precomputed values
			}
		}
		cout << ans << '\n';
	}
    return 0;
}

`