#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
typedef long long ll; 
const int N = 30 + 5; 
const int P = 998244353;
int T, n, m = 29, ans, Inv2, b[N], c[N]; 
long long pre[N]; 

int inc (int a, int b) { return (a += b) >= P ? a - P : a; }
int dec (int a, int b) { return (a -= b) < 0 ? a + P : a; }
int mul (int a, int b) { return 1ll * a * b % P; }
int fpow (int a, int b) { int ans = 1; for ( ; b; a = mul(a, a), b >>= 1) if(b & 1) ans = mul(ans, a); return ans; }

int main () {
  ios :: sync_with_stdio(0), cin.tie(0), cout.tie(0); 
  cin >> T;
  Inv2 = fpow(2, P - 2); 
  while (T--) {
    cin >> n, --n, ans = 0; 
    auto calc = [&](int n, int i) {
      int b = ((n >> i) & 1), ans = 0; 
      if(b) ans = ((n & ((1 << i) - 1)) + 1); 
      ans += ((n & (((1 << (m + 1)) - 1) ^ ((1 << (i + 1)) - 1))) >> 1); 
      return ans; 
    } ;
    rep(i, 0, m) b[i] = ((n >> i) & 1), c[i] = calc(n, i); 
    // rep(i, 0, m) cout << i << ' ' << c[i] << '\n'; 
    pre[0] = c[0]; 
    rep(i, 1, m) pre[i] = pre[i - 1] + 1ll * (1ll << i) * c[i]; 
    auto chk = [&](int u, bool lim) {
      int cur = (!lim ? ((1 << (u + 1)) - 1) : (n & ((1 << (u + 1)) - 1))); 
      // cout << "chk : " << u << ' ' << lim << ' ' << cur << '\n'; 
      rep(i, 0, u) {
        int cnt = calc(cur, i);
        // cout << i << ' ' << cnt << '\n'; 
        ans = dec(ans, mul(cnt, mul(c[i], 1 << i)));
        ans = inc(ans, mul(cur + 1 - cnt, mul(c[i], 1 << i)));   
      }
    } ;
    function <void(int, int, ll)> dfs = [&](int u, bool lim, ll w) {
      if(w <= 0 && w + pre[u] <= 0) return ; 
      // cout << u << ' ' << lim << ' ' << w << '\n'; 
      if(u == -1) return ans = inc(ans, w), void(); 
      if(w - pre[u] >= 0) {
        ans = inc(ans, mul(w % P, 1 << (u + 1))); 
        return chk(u, lim), void(); 
      }
      dfs(u - 1, lim & (!b[u]), w + 1ll * c[u] * (1 << u));
      if(!lim || (b[u] == 1)) dfs(u - 1, lim & (b[u]), w - 1ll * c[u] * (1 << u));  
    } ;
    dfs(m, 1, 0); 
    /*rep(i, 0, n) {
      ll res = 0; 
      rep(j, 0, m) {
        if((i >> j) & 1) res -= 1ll * c[j] * (1ll << j);
        else res += 1ll * c[j] * (1ll << j);
      }
      if(res > 0) ans = inc(ans, res % P); 
      // cout << i << ' ' << res << '\n'; 
    }*/
    // cout << ans << '\n'; 
    ans = inc(ans, mul(n, mul(n + 1, mul(n + 1, Inv2)))); 
    // cout << ans << '\n'; 
    int Inv = fpow(n + 1, P - 2); 
    ans = mul(ans, mul(Inv, Inv)); 
    cout << ans << '\n'; 
  }
  return 0; 
}