#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxn = 1000005, mod = 998244353;

ll prime[maxn], mu[maxn], cnt, s[maxn], pw[maxn];
bool vis[maxn];
map<ll, ll> mp;

ll ksm(ll a, ll b) {
	ll ret = 1;
	for (; b; b >>= 1, a = 1ll * a * a % mod) if (b & 1) ret = 1ll * ret * a % mod;
	return ret;
}

void init(ll mx) {
	mu[1] = pw[0] = 1;
	for (ll i = 2; i <= mx; i++) {
		if (!vis[i]) {
			prime[++cnt] = i;
			mu[i] = -1;
		}
		for (ll j = 1; j <= cnt && prime[j] * i <= mx; j++) {
			vis[prime[j] * i] = 1;
			if (i % prime[j] == 0) break;
			mu[i * prime[j]] = -mu[i];
		}
	}
	for (ll i = 1; i <= mx; i++) {
		pw[i] = (pw[i - 1] + pw[i - 1]) % mod;
		for (ll j = i, k = 1; j <= mx; j += i, k++) {
			s[j] = (s[j] + mu[k] * pw[i] % mod + mod) % mod;
		}
	}
	for (ll i = 1; i <= mx; i++) s[i] = (s[i] + s[i - 1]) % mod;
}

ll sum(ll n) {
	if (n <= 1000000) return s[n];
	if (mp.find(n) != mp.end()) return mp[n];
	ll ret = (ksm(2, n + 1) - 2 + mod) % mod;
	for (ll i = 2, j; i <= n; i = j + 1) {
		j = n / (n / i);
		ret = (ret - 1ll * (j - i + 1) * sum(n / i) % mod + mod) % mod;
	}
	return mp[n] = ret;
}

int main() {
	init(1000000);
	ll T;
	scanf("%lld", &T);
	while (T--) {
		ll n, m, ans = 0;
		scanf("%lld", &n); m = n >> 1;
		for (ll i = 1, j; i <= m; i = j + 1) {
			j = min(m, n / (n / i));
			ans = (ans + 1ll * (n / i) * (sum(j) - sum(i - 1) + mod) % mod) % mod;
		}
		ans = ((ans + ksm(2, n) - sum(m)) % mod + mod) % mod;
		printf("%lld\n", ans);
	}
	return 0;
}