Hello, PastePlz!

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1000000;
const int mod=998244353;
int mobi[N+5],len,prime[N+5],n,T,phi[N+5],mu0[N+5],mu1[N+5],mu2[N+5];
bool bz[N+5];
void init() {
	phi[1]=mobi[1]=1;
	for(int i=2; i<=N; i++) {
		if(!bz[i]) {
			len++;
			prime[len]=i;
			phi[i]=i-1;
			mobi[i]=-1;
		}
		for(int j=1; j<=len&&i*prime[j]<=N; j++) {
			bz[i*prime[j]]=true;
			if(i%prime[j]) {
				mobi[i*prime[j]]=-mobi[i];
				phi[i*prime[j]]=(long long)phi[i]*phi[prime[j]];
			} else {
				mobi[i*prime[j]]=0;
				phi[i*prime[j]]=(long long)phi[i]*prime[j];
				break;
			}
		}
	}
	for(int i=1; i<=N; i++) {
		mu0[i]=mobi[i]+mu0[i-1];
		mu1[i]=mobi[i]*i%mod+mu1[i-1];
		mu2[i]=mobi[i]*i*i%mod+mu2[i-1];
		if(mu0[i]>mod)mu0[i]-=mod;
		if(mu1[i]>mod)mu1[i]-=mod;
		if(mu2[i]>mod)mu2[i]-=mod;
	}
	return;
}
int H(int x) {
	int now((1+x)*x/2%mod);
	return now*now%mod;
}
int G(int x) {
	int now((1+x)*x/2%mod);
	return ((-2)*n*x%mod*now%mod+mod)%mod;
}
int F(int x) {
	return n*n%mod*x%mod*x%mod;
}
int h(int x) {
	int now((1+x)*x/2%mod);
	return 4*now*now%mod;
}
int g(int x) {
	int now((1+x)*x/2%mod);
	return ((-4)*n*x%mod*now%mod+mod)%mod;
}
int f(int x) {
	return n*n%mod*x%mod*x%mod;
}
signed main() {
	cin>>T;
	init();//预处理mu,mu*i,mu*i*i
	while(T--) {
		cin>>n;
		int ans(0);
		for(int l=1,r; l<=n; l=r+1) {
			r=n/(n/l);
			ans+=F(n/l)*(mu0[r]-mu0[l-1])%mod;
			ans+=mod;
			ans%=mod;
			ans+=G(n/l)*(mu1[r]-mu1[l-1])%mod;
			ans+=mod;
			ans%=mod;
			ans+=H(n/l)*(mu2[r]-mu2[l-1])%mod;
			ans+=mod;
			ans%=mod;
		}
		for(int l=1,r; l<=n/2; l=r+1) {
			r=n/(2*(n/(2*l)));
			ans-=f(n/(2*l))*(mu0[r]-mu0[l-1])%mod;
			ans+=mod;
			ans%=mod;
			ans-=g(n/(2*l))*(mu1[r]-mu1[l-1])%mod;
			ans+=mod;
			ans%=mod;
			ans-=h(n/(2*l))*(mu2[r]-mu2[l-1])%mod;
			ans+=mod;
			ans%=mod;
		}
		//	cout<<(2*ans+2*n+4*n-6)*499122177%mod<<'\n';//ans是所有k>0的直线的个数和，不论夹角是否小于45度
		cout<<(ans+3*n-3)%mod<<'\n';
	}
	return 0;
}