#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int iu=1e7;
ll phi[iu+1];
const ll mod=1e6+3;
ll p0[iu+1],p1[iu+1],p2[iu+1];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	for(int i=1; i<=iu ;i++){
		phi[i]+=i;
		for(int j=i*2; j<=iu ;j+=i){
			phi[j]-=phi[i];
		}
	}
	p0[1]=p1[1]=p2[1]=1;
	for(int i=2; i<=iu ;i++){
		p0[i]=(p0[i-1]+phi[i]*2)%mod;
		p1[i]=(p1[i-1]+phi[i]*i%mod+phi[i]*i/2%mod)%mod;
		p2[i]=(p2[i-1]+phi[i]*i%mod*i%mod)%mod;
		//cout << p0[i] << ' ' << p1[i] << ' ' << p2[i] << endl;
	}
	int t;cin >> t;
	while(t--){
		ll n;cin >> n;
		if(n==1){
			cout << "0\n";
			continue;
		}
		ll ans=n;
		{
			ans=(ans-n*n%mod*p0[n/2]+4*p1[n/2]*n-4*p2[n/2])%mod;
			ans=(ans+n*n%mod*p0[n]-2*p1[n]*n+p2[n])%mod;
			ans=(ans+mod)%mod;
			
		}
		ans=(ans*2)%mod;
		cout << ans << '\n';
	}
}