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

int get() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)) { if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

const int N = 1e7 + 5, P = 1e6 + 3;
int pri[N], tot, vis[N], mu[N], phi[N];
int sp[N], s2m[N], sm[N], S2[N], S3[N];

void init(int n) {
	phi[1] = mu[1] = 1;
	for(int i = 2; i <= n; i++) {
		if(!vis[i]) mu[i] = -1, phi[i] = i - 1, pri[++tot] = i;
		for(int j = 1; j <= tot && i * pri[j] <= n; j++) {
			vis[i * pri[j]] = 1;
			if(i % pri[j] == 0) { mu[i * pri[j]] = 0, phi[i * pri[j]] = phi[i] * pri[j]; break; }
			mu[i * pri[j]] = -mu[i], phi[i * pri[j]] = phi[i] * (pri[j] - 1);
		}
	}
	for(int i = 1; i <= n; i++) {
		sp[i] = (sp[i - 1] + i * phi[i]) % P;
		sm[i] = (sm[i - 1] + i * mu[i]) % P;
		s2m[i] = (s2m[i - 1] + i * i * mu[i]) % P;
		S2[i] = (S2[i - 1] + i * (i + 1) / 2) % P;
		S3[i] = (S3[i - 1] + i * (i + 1) / 2 % P * i) % P;
		phi[i] = (phi[i] + phi[i - 1]) % P;
	}
}

void solve(int n) {
	if(n == 1) return printf("0\n"), void();
	int ans = 0;
	ans += 4 * n * sp[n] % P;
	for(int i = 1, j; i <= n; i = j + 1) {
		j = min(n, n / (n / i));
		ans = (ans + 4 * n * (sm[j] - sm[i - 1]) % P * S2[n / i]) % P;
		ans = (ans - 12 * (s2m[j] - s2m[i - 1]) % P * S3[n / i]) % P;
	}
	int lbi = n / 2 + 1;
	ans = (ans + 4 * n * n % P * (phi[n] - phi[lbi - 1])) % P;
	ans = (ans - 8 * n * (sp[n] - sp[lbi - 1])) % P;
	for(int i = 1, j; i <= n; i = j + 1) {
		j = min(n, n / (n / i));
		int lb = (lbi + i - 1) / i;
		ans = (ans - 8 * n * (sm[j] - sm[i - 1]) % P * (S2[n / i] - S2[lb - 1])) % P;
		ans = (ans + 16 % P * (s2m[j] - s2m[i - 1]) % P * (S3[n / i] - S3[lb - 1])) % P;
	}
	ans = (ans + 2 * n - ((n - 1) * (n - 1) % P - (n - 2) * (n - 2) % P) * 2 % P) % P;
	ans = (ans % P + P) % P;
	printf("%lld\n", ans);
}

main() {
	int T = get();
	init(10000000);
	while(T--) solve(get());
	return 0;
}