#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<bitset>
#include<vector>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 10000005
#define LL long long
#define DB double
#define ENDL putchar('\n')
#define lowbit(x) (-(x)&(x))
inline LL read() {
	LL f=1,x=0;int s=getchar();
	while(s<'0'||s>'9') {if(s<0)return -1;if(s=='-')f=-f;s=getchar();}
	while(s>='0'&&s<='9') {x=(x<<3)+(x<<1)+(s^48);s=getchar();}
	return f*x;
}

const int MOD = 1000003;
int n,m,s,o,k;
bool f[MAXN];
int mu[MAXN],phi[MAXN],p[MAXN],cnp,sp[MAXN];
int smu[MAXN],sud[MAXN],sud2[MAXN];
void sieve(int n) {
	f[1] = 1; mu[1] = phi[1] = 1; cnp = 0;
	sp[1] = 1; smu[1] = sud[1] = sud2[1] = 1;
	for(int i = 2;i <= n;i ++) {
		if(!f[i]) {
			p[++ cnp] = i;
			mu[i] = MOD-1;
			phi[i] = i-1;
		}
		smu[i] = (smu[i-1] + mu[i]) % MOD;
		sud[i] = (sud[i-1] + mu[i]*1ll*i) % MOD;
		sud2[i] = (sud2[i-1] + mu[i]*1ll*i%MOD*i) % MOD;
		sp[i] = (phi[i]*1ll*i/2) % MOD;
		phi[i] %= MOD;
		for(int j = 1;j <= cnp && i*p[j] <= n;j ++) {
			int x = i*p[j]; f[x] = 1;
			if(i % p[j] == 0) {
				mu[x] = 0; phi[x] = phi[i] * p[j];
				break;
			}
			mu[x] = MOD-mu[i]; phi[x] = phi[i] * phi[p[j]];
		}
	}
	return ;
}
const int inv6 = 5000016/6;
int SM(int x) {return ((x+1)*1ll*x/2)%MOD;}
int SM2(int x) {return x*1ll*(x+1)%MOD*(x+x+1)%MOD*inv6%MOD;}
int SMS(int d,int n) {return SM(n/d)*1ll*d%MOD;}
int CN(int d,int l,int r) { // (l,r]
	return (r/d - l/d) % MOD;
}
int CNS(int d,int l,int r) {
	return (SM(r/d) +MOD- SM(l/d)) % MOD;
}
int pw(int x) {return x*1ll*x%MOD;}
int main() {
	sieve(10000000);
	int Q = read();
	while(Q --) {
		n = read();
		// cerr<<"OK"<<endl;
		if(n == 1) {putchar('0');ENDL;continue;}
		LL ans = 0;
		int N = n/2,np = n*1ll*n %MOD;
		for(int d = 1;d < n;d ++) {
			int rr;
			if(d <= N) rr = min(N/(N/d),(n-1)/((n-1)/d));
			else rr = (n-1)/((n-1)/d);
			int su = (smu[rr]+MOD-smu[d-1]) % MOD;
			int sd = (sud[rr]+MOD-sud[d-1]) % MOD;
			int sd2 = (sud2[rr]+MOD-sud2[d-1]) % MOD;
			int c = (N/d),s = SM(N/d);
			ans = (0ll+ans + c*2ll*s%MOD*n%MOD*sd%MOD +MOD- s*3ll*s%MOD*sd2%MOD) % MOD;
			// cerr<<"d:"<<d<<" ans:"<<ans<<endl;
			int c2 = CN(d,N,n-1),s2 = CNS(d,N,n-1);
			ans = (0ll+ans + (c*1ll*c2%MOD*np%MOD*su%MOD +MOD- (c*1ll*s2 + c2*1ll*s)%MOD*n%MOD*sd%MOD + s*1ll*s2%MOD*sd2%MOD)*2ll%MOD) % MOD;
			// cerr<<"d:"<<d<<" ans:"<<ans<<endl;
			ans = (0ll+ans + c2*1ll*c2%MOD*np%MOD*su%MOD +MOD- c2*2ll*s2%MOD*n%MOD*sd%MOD + s2*1ll*s2%MOD*sd2%MOD) % MOD;
			// cerr<<"d:"<<d<<" ans:"<<ans<<endl;
			d = rr;
		}
		ans = (ans *2ll % MOD + n + n) % MOD;
		printf("%lld\n",ans);
	}
	return 0;
}