#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long double D;
typedef pair<int, int> pii;
typedef long long LL;
const int inf = 1e9 + 7;
const int mod = 1000003;
const int N = 10000011;
const int L = 10000000;
int np = 0;
int primes[N], f[N], mu[N], smu[N], mnp[N];
LL calc(int n) {
	return (1ll + n) * n / 2 % mod * (((1ll + n) * n / 2) % mod) % mod;
}
int solve(int n) {
	if(n == 0) return 0;
	int res = 0;
	int i = 1;
	for(;;) {
		
		int div = n / i;
		int nxt = n / div + 1;
		//cout << n << ' ' << i << ' ' << nxt << endl;
		res = (res + calc(div) * (smu[nxt - 1] - smu[i - 1] + mod) % mod) % mod;
		//cout << calc(div) << ' ' << (smu[nxt - 1] - smu[i - 1]) << endl;
		i = nxt;
		if(i > n) break;
	}
	//cout << "s" << n << ' ' << res << endl;
	return res;
}
int main() {
	mu[1] = 1;
	primes[0] = inf;
	fill(f + 2, f + L + 1, true);
	for(int i = 2; i <= L; i++) {
		if(f[i]) {
			primes[++np] = i;
			mnp[i] = np;
			mu[i] = -1;
		}
		for(int j = 1; j <= np && primes[j] * i <= L && i % primes[j - 1]; j++) {
			f[primes[j] * i] = false;
			mnp[primes[j] * i] = j;
			if(mnp[primes[j] * i] == mnp[i]) {
				mu[primes[j] * i] = 0;
			}else {
				mu[primes[j] * i] = -1 * mu[i];
			}
		}
	}
	for(int i = 1; i <= L; i++) {
		//if(i <= 10) printf("%d %d %d\n", i, mu[i], smu[i]);
		smu[i] = (smu[i - 1] + mu[i] + mod) % mod;
	}
	//cout << "!" << endl;
	int Q;
	scanf("%d", &Q);
	for(int i = 1; i <= Q; i++) {
		int n;
		scanf("%d", &n);
		n--;
		int ans = (solve(n) - solve(n / 2) + mod) % mod;
		//cout << "a" << ans << endl;
		ans = ans * 2 % mod;
		ans = (ans + 2 + n * 2) % mod;
		if(n == 0) ans = 0;
		printf("%d\n", ans);
	}
}