#include<bits/stdc++.h>
using namespace std;
#define int long long
int read(){
	int f = 1,x = 0;
	char c = getchar();
	while(c > '9' || c < '0'){
		if(c == '-') f = -1;
		c = getchar();
	}
	while(c >= '0' && c <= '9'){
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}
const int maxn = 10000005;
int ff[maxn];
int miu[maxn],sum[maxn];
bool vis[maxn];
int su[2000005],cnt;
const int mod = 1000003;
int summ[maxn];
void init(int nn)
{
	for(int i=1;i<=nn;++i) ff[i] = i * i % mod * (i + 1) % mod;
	miu[1] = 1;
	for(int i=2;i<=nn;++i){
		if(!vis[i]){
			cnt ++;
			su[cnt] = i;
			miu[i] = -1;
		}
		for(int j=1;j<=cnt && su[j] * i <= nn;++j){
			vis[i * su[j]] = 1;
			miu[i*su[j]] = miu[i] * miu[su[j]];
			if(i % su[j] == 0){
				miu[i * su[j]] = 0;
				break;
			}
		}
	}
	for(int i=1;i<=nn;++i) sum[i] = sum[i-1] + miu[i];
	for(int i=1;i<=nn;++i) summ[i] = summ[i-1] + miu[i] * i,summ[i] %= mod;
}
signed main()
{
	init(maxn - 5);
	int q = read();
	while(q != 0){
		--q;
		int n = read();
		int ans = 0;
		int r = 0;
		--n;
		for(int l = 1;l <= n;l = r + 1)
		{//n/i = n/l
			r = n/(n/l);
			ans += (sum[r] - sum[l-1]) * (2 * n + 1) % mod * (n/l) % mod * (n/l) % mod;
			ans %= mod;
			int d = n/l;
			ans -= ff[n/l] * (summ[r] - summ[l-1]) % mod;
			ans %= mod;
		}
		ans *= 2; ans %= mod;
		++n;
		if(n != 1) ans += 2 * n;
		ans %= mod;
		ans += mod;
		ans %= mod;
		printf("%lld\n",ans);
	}
}