// すいません，yukicoder が遅すぎます（オンライン実行で 10+sec）
// あるいは，手元が速すぎます（2.3sec）

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<atcoder/modint>
using namespace std;
using mint = atcoder::modint998244353;

void solve(){
    uint64_t n; cin >> n;
    n = n * 2 + 1;
    uint64_t m = sqrt(n);
    while ((m+1)*(m+1) <= n) m++;
    while (m*m > n) m--;
    uint64_t sum = 0;
    for (uint64_t i = 1; i <= m; i += 2){
        sum += (n + i) / (i * 2);
    }
    mint ans = sum;
    ans *= 2;
    ans -= mint((m+1)/2).pow(2);
    ans -= n;
    cout << ans.val() << '\n';
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int t; cin >> t;
    while (t--){
        solve();
    }
}