#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define x first
#define y second

using namespace std;

typedef long double ld;
typedef long long ll;

const int MOD = 998244353;

vector <pair <int, int> > segments;
ll koef[35];

int cnt_ones(int n, int bit)
{
 	if (n <= 0) return 0;
 	int a = (n >> (bit + 1));
 	int ans = (a << bit);
 	if (n >= (a << (bit + 1)) + (1 << bit)) ans += n - (a << (bit + 1)) - (1 << bit) + 1;
 	return ans;
}

int cnt_ones(int lef, int rig, int bit)
{
	return cnt_ones(rig, bit) - cnt_ones(lef - 1, bit); 	
}

void gener(int x, int n)
{
 	if (x >= n)
 	{
 	 	segments.back().y = n - 1;
 	 	return; 
 	}

 	ll sum = 0;
 	for (int bit = 0; bit <= 29; bit++)
 		if ((x >> bit) & 1) sum -= koef[bit];
 		else sum += koef[bit];

 	if (sum >= 0)
 	{
 	 	for (int bit = 0; bit <= 29; bit++)
 	 	{
 	 		if ((x >> bit) & 1) continue;
 	 		ll poten = 0;
 	 		for (int i = 29; i > bit; i--)
 	 			if ((x >> i) & 1) poten -= koef[i];
 	 			else poten += koef[i];
 	 		poten -= koef[bit];
 	 		for (int i = bit - 1; i >= 0; i--) poten -= koef[i];
 	 		if (poten >= 0) continue;

 	 		int new_x = ((x >> (bit + 1)) << (bit + 1)) + (1 << (bit + 1)) - 1;
 	 		for (int i = bit - 1; i >= 0; i--)
 	 		{
 	 		 	if (poten + 2 * koef[i] < 0)
 	 		 	{
 	 		 	 	poten += 2 * koef[i];
 	 		 	 	new_x -= (1 << i);
 	 		 	}
 	 		}
 	 		segments.pb(mp(x, new_x - 1));
 	 		gener(new_x, n);
 	 		return;
 		}
 		segments.pb(mp(x, n - 1));
 	}
 	else
 	{
 		for (int bit = 0; bit <= 29; bit++)
 	 	{
 	 		if ((x >> bit) & 1) continue;
 	 		ll poten = 0;
 	 		for (int i = 29; i > bit; i--)
 	 			if ((x >> i) & 1) poten -= koef[i];
 	 			else poten += koef[i];
 	 		poten -= koef[bit];
 	 		for (int i = bit - 1; i >= 0; i--) poten += koef[i];
 	 		if (poten < 0) continue;

 	 		int new_x = ((x >> (bit + 1)) << (bit + 1)) + (1 << bit);
 	 		segments.pb(mp(x, new_x - 1));
 	 		gener(new_x, n);
 	 		return;
 		}
 		segments.pb(mp(x, n - 1));
 	}
 	return;
}

int binpow(int x, int step)
{
 	int res = 1;
 	while (step > 0)
 	{
 	 	if (step & 1) res = (ll) res * x % MOD;
 	 	x = (ll) x * x % MOD;
 	 	step /= 2;
 	}
 	return res;
}

int main()
{
 	//freopen("input.txt", "r", stdin);
 	//freopen("output.txt", "w", stdout);
	ios_base::sync_with_stdio(0); cin.tie(0);

	int test;
	cin >> test;
	for (int rep = 1; rep <= test; rep++)
	{
	 	int n;
	 	cin >> n;
	 	if (n == 1) {cout << "0\n"; continue;}

	 	for (int i = 0; i <= 29; i++) koef[i] = (1ll << i) * cnt_ones(0, n - 1, i);
	 	segments.clear();
	 	gener(0, n);

	 	int rev_n = binpow(n, MOD - 2);
	 	int rev_2 = binpow(2, MOD - 2);

	 	int ans = (ll) (n - 1) * rev_2 % MOD;
	 	int sum = 0;
	 	for (int i = 0; i < (int) segments.size(); i++)
	 	{
	 	 	if (i & 1) continue;

	 	 	for (int bit = 0; bit <= 29; bit++)
	 	 	{
	 	 	 	int s = (1ll << bit) * cnt_ones(0, n - 1, bit) % MOD;
	 	 	 	s = (ll) s * (segments[i].y - segments[i].x + 1 - 2 * cnt_ones(segments[i].x, segments[i].y, bit)) % MOD;
	 	 	 	sum = (sum + s) % MOD;
	 	 	}
	 	}
	 	ans = (ans + (ll) sum * rev_n % MOD * rev_n) % MOD;
	 	cout << ans << '\n';
	}

	return 0;
}