正经题解

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6, M = 998244353;
int v[N+1];
ll p[N+1], q[N+1], iv[N+1];
int main() {
    for (int i = 2; i <= N; ++i)
        v[i] = (i & 1) ? 0 : v[i>>1] + 1;
    for (int i = 1; i <= N; ++i) {
        p[i] = p[i-1] + v[i];
        q[i] = (q[i-1] + (ll)i * v[i]) % M;
    }
    iv[1] = 1;
    for (int i = 2; i <= N; ++i)
        iv[i] = M - (ll)(M/i) * iv[M % i] % M;
    int t, n;
    cin >> t;
    while (t--) {
        cin >> n;
        ll d = (ll)n * (n - 1) % M;
        ll s = ((ll)n * (p[n-1] % M) - q[n-1] + M) % M;
        ll a = (d + 2 * s) % M;
        ll r = a * iv[n] % M * iv[n-1] % M;
        cout << r << '\n';
    }
    return 0;
}