#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
using LL = long long;
int n;

// [0, x)
int calc(int x, int w) {
    int v1 = 1 << w;
    int rep = v1 * 2;
    int ret = x / rep * v1;
    int rem = x % rep;
    if (rem > v1) {
        ret += rem - v1;
    }
    return ret;
}

int calc2(int x) {
    int ret = 0;
    //printf("x = %d, n = %d\n",x,n);
    for (int w = 0; w < 30; w++) {
        int v1_1 = calc(x + 1, w);
        int v1_0 = x + 1 - v1_1;
        int v2_1 = calc(n, w);
        int v2_0 = n - v2_1;
        //printf("%d %d %d %d\n",v1_1,v1_0,v2_1,v2_0);
        ret = (ret + (1LL * v1_1 * v2_0 + 1LL * v1_0 * v2_1) % MOD * (1LL << w) % MOD) % MOD;
    }
    return ret;
}

// a \in [l, r], b \in [0, n), \sum(a ^ b)
int getsum(int l, int r) {
    return (calc2(r) - calc2(l - 1) + MOD) % MOD;
}

int quick_pow(int a, int x) {
    int ret = 1;
    while(x) {
        if (x & 1) {
            ret = 1LL * ret * a % MOD;
        }
        a = 1LL * a * a % MOD;
        x >>= 1;
    }
    return ret;
}

int seqsum(int l, int r) {
    return 1LL * (r + l) * (r - l + 1) / 2 % MOD;
}

int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        scanf("%d",&n);
        int ans = calc2(0);
        for (int w = 0; w < 30; w++) {
            // hight bit = 2^w
            if ((1 << w) >= n) {
                break;
            }
            int L = (1 << w) - 1, R = (1 << (w + 1));
            if ((1 << (w + 1)) >= n) {
                R = n;
            }
            // need to xor
            auto check = [&](int x) {
                LL v1 = 1LL * x * n;
                LL v2 = getsum(x, x);
                return v2 >= v1;
            };
            while(L < R - 1) {
                int mid = (L + R) >> 1;
                if (check(mid)) {
                    L = mid;
                } else {
                    R = mid;
                }
            }
            // printf("w = %d, L = %d, R = %d\n", w, L, R);
            ans = (ans + 1LL * seqsum(R, min((1 << (w + 1)) - 1, n - 1)) * n) % MOD;
            ans = (ans + getsum(1 << w, L)) % MOD;
            // printf("ans = %d\n", ans);
        }
        ans = 1LL * ans * quick_pow(n, MOD - 2) % MOD;
        ans = 1LL * ans * quick_pow(n, MOD - 2) % MOD;
        printf("%d\n", ans);
    }
}