#include<bits/stdc++.h>
using namespace std;

#define ll long long

const int maxn=1e7+10;
const int N=1e7;
const int mod=1e6+3;

int prime[maxn];
bool vis[maxn];
int mu[maxn];
int mud[maxn];
int mudd[maxn];
int p_cnt;

void sieve()
{
	mu[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!vis[i]) prime[++p_cnt]=i,mu[i]=-1;
		for(int j=1;j<=p_cnt;j++)
		{
			if(i*prime[j]>N) break;
			vis[i*prime[j]]=1;
			if(i%prime[j]==0) break;
			mu[i*prime[j]]=mod-mu[i];	
		}
	}
	for(int i=1;i<=N;i++) mudd[i]=(1ll*mu[i]*i*i+mudd[i-1])%mod,mud[i]=(1ll*mu[i]*i+mud[i-1])%mod,mu[i]=(mu[i]+mu[i-1])%mod;
}

int main()
{
	int q;
	sieve();
	scanf("%d",&q);
	while(q--)
	{
		int n;
		scanf("%d",&n);
		if(n==1)
		{
			printf("0\n");
			continue;
		}
		ll ans=n*2;
		for(int l=1,r;l<=n-1;l=r+1)
		{
			int x=(n-1)/l;
			r=min(n-1,(n-1)/x),ans+=2ll*n*n%mod*(mu[r]-mu[l-1]+mod)%mod*x%mod*x%mod+mod-2ll*n*(mud[r]-mud[l-1]+mod)%mod*x%mod*x%mod*(x+1)%mod+2ll*(mudd[r]-mudd[l-1]+mod)*(1ll*x*(x+1)/2%mod)%mod*(1ll*x*(x+1)/2%mod)%mod;
		}
		for(int l=1,r;l<=n/2;l=r+1)
		{
			int x=n/2/l;
			r=min(n/2,n/2/x),ans+=mod-2ll*n*n%mod*(mu[r]-mu[l-1]+mod)%mod*x%mod*x%mod+4ll*n*(mud[r]-mud[l-1]+mod)%mod*x%mod*x%mod*(x+1)%mod+mod-8ll*(mudd[r]-mudd[l-1]+mod)*(1ll*x*(x+1)/2%mod)%mod*(1ll*x*(x+1)/2%mod)%mod;
		}
		printf("%lld\n",ans%mod);
	}
	return 0;
}