rt，求 $1\sim n$ 质数个数我写的是 Lucy DP（见 https://atcoder.jp/contests/abc370/editorial/10906），理论单次复杂度 $O(\frac{n^{\frac 34}}{\log n})$，加上多测大概运算量 $6\times 10^8$，现在只有 #7 和 #9 超时，跑了 2.62s 左右，想不到什么很好的卡常方法了。

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,ll> pil;
#define fi first
#define se second
#define endl '\n'
#define mkp make_pair
#define pb push_back
#define all(x) x.begin(),x.end()
#define Cl(x) memset(x,0,sizeof(x))
const bool DC=1;
const ll mod=998244353;
const int N=160005;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll qpow(ll a,ll b,ll p=mod){ll ans=1;for(;b;b>>=1,a=a*a%p)if(b&1)ans=ans*a%p;return ans;}
void NO(){cout<<"NO\n";}
void YES(){cout<<"YES\n";}
mt19937 rnd((unsigned long long)new char);
int rnad(){return abs((int)rnd());}
int rd(int l,int r){return rnad()%(r-l+1)+l;}

ll n;
ll calc(ll n){
	ll sn=sqrtl(n);
	vector<ll>q;
	cc_hash_table<ll,ll>s;
	for(ll l=1,r;l<=n;l=r+1)r=n/(n/l),q.push_back(r),s[r]=r-1;
	reverse(all(q));
	for(ll x=2;x<=sn;x++)if(s[x]>s[x-1])for(auto m:q)if(m<x*x)break;
	else s[m]-=s[m/x]-s[x-1];
	return s[n];
}

void __INIT__(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);;}
void __SOLVE__(int _case){
	cin>>n;
	if(n==3)return cout<<"4\n",void();
	bool isp=1;
	for(int i=2;i*i<=n;i++)if(n%i==0){isp=0;break;}
	cout<<(qpow(2,calc(n)-calc(n/2))+1+isp)%mod<<"\n";
}
int main(){
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	__INIT__();int T;DC?cin>>T,1:T=1;for(int _CASE=1;_CASE<=T;_CASE++)__SOLVE__(_CASE);return 0;}