#include<bits/stdc++.h>
#define fs(i,x,y) for(int i=(x),_=(y);i<=_;++i)
#define fn(i,x,y) for(int i=(x),_=(y);i>=_;--i)
#define int ll
using namespace std;
typedef long long ll;
typedef double db;

const int N = 1e5 + 7, P = 998244353, iv2 = (P + 1) / 2;
int n;
int cnt[N];
//zhuyi bao longlong

int qw(int a, int b) {
    int ans = 1;
    for (;b;a = (ll)a * a % P, b >>= 1)if (b & 1)ans = (ll)ans * a % P;
    return ans;
}

void pre() {
    int lim = 2;
    fs(i, 0, 30) {
        int tp = n % lim;
        cnt[i] = (n - tp) / 2;
        if ((tp >> i) & 1) {
            cnt[i] += (n % (lim >> 1)) + 1;
        }
        // cout << i << ' ' << cnt[i] << endl;
        cnt[i] *= (lim >> 1);
        lim <<= 1;
    }
    // fs(i, 0, 30)cout << cnt[i] << ' ';
    // cout << endl;
}

bool calc(int x) {
    ll tp = 0;
    fn(i, 30, 0) {
        if ((x >> i) & 1) {
            tp -= cnt[i];
        }
        else tp += cnt[i];
    }
    return tp > 0;
}

int qry(int l, int r) {
    int ans = l - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (calc(mid))ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    return ans;
}

int sol(int dig, int l, int pos) {
    if (pos < l)return 0;
    int ans = 0;
    fs(i, dig + 1, 30) {
        ans = (ans + cnt[i] % P * (pos - l + 1) % P) % P;
    }
    ans = (ans - cnt[dig] % P * (pos - l + 1) % P + P) % P;
    int lim = 2;
    fs(i, 0, dig - 1) {
        if ((pos >> i) & 1) {
            ans = (ans + cnt[i] % P * ((lim >> 1) - 1 - (pos % (lim >> 1))) % P) % P;
            // cout << ((lim >> 1) - 1 - (pos % (lim >> 1))) << " " << "jishu" << "///";
        }
        else {
            ans = (ans + cnt[i] % P * ((pos % (lim >> 1)) + 1) % P) % P;
            // cout << pos % (lim >> 1) + 1 << ' ' << "oushu" << "///";
        }
        lim <<= 1;
    }
    return ans;
}

void solve() {
    scanf("%lld", &n);
    --n;
    pre();
    // fs(i, 0, n) {
    //     cout << calc(i) << ' ' << i << endl;
    // }
    int ans = n * (n + 1) % P * (n + 2) % P * iv2 % P;
    // cout << ans << endl;
    // cout << "HHH" << endl;
    for (int i = 0;;++i) {
        int l = (1ll << i), r = min((1ll << (i + 1)) - 1, n);
        if (l > n)break;
        // cout << "HHH" << endl;
        int pos = qry(l, r);
        // cout << pos << endl;
        // cout << "///";
        // cout << pos << ' ' << sol(i, l, pos) << endl;
        ans += sol(i, l, pos);
        // cout << endl;
        // ans += (l + r) * (r - l + 1) % P * iv2 % P * n % P;
    }
    // cout << ans << endl;
    // cout << "abs" << endl;
    printf("%lld\n", ans * qw(n + 1, P - 2) % P * qw(n + 1, P - 2) % P);
}

signed main() {
    // freopen("in", "r", stdin);
    // freopen("hhout", "w", stdout);
    // cout << 6 << endl;
    // fs(i, 5000, 5005)cout << i << endl;
    int T = 0;
    scanf("%lld", &T);
    while (T--) {
        solve();
    }
}