#include <bits/stdc++.h>

using namespace std;

const int mod = 998244353;

int modpow(int64_t e, int p) {
    int64_t r = 1;
    while (p) {
        if (p & 1) r = r * e % mod;
        e = e * e % mod;
        p >>= 1;
    }
    return r;
}

vector<pair<int64_t,int>> gen(int64_t h[]) {
    vector<pair<int64_t,int>> ret, u, v;
    ret.reserve(1 << 15);
    u.reserve(1 << 15);
    v.reserve(1 << 15);

    ret.emplace_back(0, 0);

    for (int i = 15 - 1; i >= 0; i--) {
        u.clear();
        v.clear();
        for (size_t j = 0; j < ret.size(); j++) {
            u.emplace_back(ret[j].first - h[i], ret[j].second + (1 << i));
            v.emplace_back(ret[j].first + h[i], ret[j].second);
        }
        ret.resize(u.size() + v.size());
        merge(u.begin(), u.end(), v.begin(), v.end(), ret.begin());
    }
    return ret;
}

void solve(int n) {
    int64_t h[30];
    for (int i = 0; i < 30; i++) {
        int L = (1 << i);
        // h[i] = ((n - 1) / L + 1) / 2;
        h[i] = (n / L) / 2 * L + 
            
            ((n / L) % 2 == 1 ? n % L : 0);
    }

    // for (int i = 0; i < 30; i++) {
    //     int cnt = 0;
    //     for (int j = 0; j < n; j++) {
    //         cnt += (j >> i & 1);
    //     }
    //     // h[i] = cnt;
    //     cerr<<cnt<<','<<h[i]<<' '<<n<<endl;
    //     assert (cnt == h[i]);
    // }

    // return;

    for (int i = 0; i < 30; i++)
        h[i] <<= i;


    auto lo = gen(h);
    auto hi = gen(h + 15);
    // cerr << "|lo| = " << lo.size() << endl;
    // cerr << "|hi| = " << hi.size() << endl;

    reverse(lo.begin(), lo.end());

    const int L = (n >> 15);

    size_t it = 0;
    int64_t sum = 0;
    int64_t cnt = 0;
    int64_t ans = 0;
    // for (auto [s1, k1]: hi) {
    //     if (k1 <= 1) {
    //         for (auto [s2, k2]: lo) {
    //             if (s1 + s2 > 0 && (k1 << 15) + k2 < n) {
    //                 ans += s1 + s2;
    //             }
    //             // if ((k1 << 15) + k2 < n)
    //             //     cerr << s1 + s2 << ' ' << k1 << ' ' << k2 << endl;
    //         }
    //     }
    // }

    for (auto [s1, k1]: hi) {
        while (it < lo.size() && lo[it].first + s1 > 0) {
            sum += lo[it].first;
            cnt += 1;
            ++it;
        }
        if (k1 < L) {
            ans = (ans + s1 * cnt + sum) % mod;
        } else if (k1 == L) {
            for (auto [s2, k2]: lo) {
                if (s1 + s2 > 0 && (k1 << 15) + k2 < n) {
                    ans = (ans + s1 + s2) % mod;
                }
            }
        }
    }

    // cerr << "n = " << n <<  endl;
    // cerr << "ans = " << ans << endl;
    ans = 1LL * ans * modpow(1LL * n * n, mod - 2) % mod;
    ans = (ans + 1LL * (n - 1) * modpow(2, mod - 2)) % mod;
    cout << ans << '\n';
}


signed main() {
    cin.tie(nullptr) -> sync_with_stdio(false);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        solve(n);
    }
}