#include<bits/stdc++.h>
using namespace std;
const int maxn=10010000;
const int n=10000000;
const int mod=1000003;
int isprime[maxn],mu[maxn],phi[maxn];
int sumphi[maxn],sumnphi[maxn];
int sumnmu[maxn];
inline void init() {
	for(int i=1;i<=n;i++) {
		isprime[i]=i!=1;
		mu[i]=1;
		phi[i]=i;
		if(i==1) phi[1]=0;
	}
	for(int i=2;i<=n;i++) if(isprime[i]) {
		for(int j=i;j<=n;j+=i) {
			if(j!=i) isprime[j]=0;
			phi[j]=phi[j]/i*(i-1);
			if(j%(i*i)==0) mu[j]=0;else mu[j]=-mu[j];
		}
	}
	//for(int i=1;i<=10;i++) cout<<mu[i]<<' ';
	//cout<<endl;
	for(int i=1;i<=n;i++) {
		sumphi[i]=(sumphi[i-1]+phi[i])%mod;
		sumnphi[i]=(sumnphi[i-1]+1ll*i*phi[i])%mod;
		sumnmu[i]=(sumnmu[i-1]+i*mu[i]%mod+mod)%mod;
	}
}

inline int ksm(int a,int b){
	int res=1;
	for(;b;b>>=1,a=1ll*a*a%mod) if(b&1) res=1ll*res*a%mod;
	return res;
}
const int inv6=ksm(6,mod-2);

inline int getans(int n) {
	int ans=(6*n-6)%mod;
	int s=0;
	s=1ll*(2*n-1)*sumphi[n-1]%mod;
	s=(s-sumnphi[n-1]+mod)%mod;
	//cout<<"fdjsklfsdlkj "<<s<<endl;
	n--;
	for(int l=1,r;l<=n;l=r+1) {
		r=n/(n/l);
		int t=n/l;
		int ad1=1ll*t*(t+1)/2%mod*t%mod;
		int ad2=1ll*t*(t+1)%mod*(2*t+1)%mod*inv6%mod;
		int adv=1ll*(sumnmu[r]-sumnmu[l-1]+mod)%mod*(ad1-ad2+mod)%mod;
		s=(s-adv)%mod;
		//s=(s-adv)%mod;
	}
//	for(int i=1;i<=n;i++) {
//		int t=n/i;
//		int ad1=t*t*(t+1)/2;
//		int ad2=t*(t+1)*(2*t+1)/6;
//		int adv=1ll*mu[i]*i*(ad1-ad2);
//		//cout<<ad1<<' '<<ad2<<endl;
//		s=(s-adv)%mod;
//	}
	
	//cout<<s<<endl;
	s=(s+mod)%mod;
	ans=(ans+4*s)%mod;
	return ans;
}
int main() {
	init();
	int n;
	cin>>n;
	int x;
	while(cin>>x) cout<<getans(x)<<endl;
}