#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], smu1[N], smu2[N], s2u[N], s2u1[N], s2u2[N], mnp[N], s2[N];
LL calc(int n) {
	return (1ll + n) * n / 2 % mod * (((1ll + n) * n / 2) % mod) % mod;
}
LL integral(LL L, LL R, LL C2, LL C1, LL C0) {
	//cout << L << ' ' << R << ' ' << C2 << ' ' << C1 << ' ' << C0 << endl;
	LL res = (smu2[R] - smu2[L - 1]) * C2 % mod + (smu1[R] - smu1[L - 1]) * C1 % mod + (smu[R] - smu[L - 1]) * C0 % mod;
	//cout << res << endl;
	return (res % mod + mod) % mod;
}
LL integral2(LL L, LL R, LL C2, LL C1, LL C0) {
	LL res = (s2u2[R] - s2u2[L - 1]) * C2 % mod + (s2u1[R] - s2u1[L - 1]) * C1 % mod + (s2u[R] - s2u[L - 1]) * C0 % mod;
	return (res % mod + 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;
		LL A = (div + 1) * div / 2 % mod;
		LL B = (div - 1) * div / 2 % mod;
		LL X = (((div + 1) * B - div * A) % mod + mod) % mod;
		LL Y = (n + 1) * (A - B) % mod;
		//cout << X << ' ' << Y << endl;
		res = (res + integral(i, nxt - 1, X * X % mod, 2 * X * Y % mod, Y * Y % mod)) % mod;
		//cout << "res  = " << res << endl;
		res = (res - integral2(i, nxt - 1, X * X % mod, 2 * X * Y % mod, Y * Y % 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];
			}
		}
	}
	int cnt = 0;
	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;
		smu1[i] = (smu1[i - 1] + mu[i] * i % mod + mod) % mod;
		smu2[i] = (smu2[i - 1] + mu[i] * i * (LL)i % mod + mod) % mod;
		int m2 = (i % 2 == 0 ? mu[i / 2] : 0);
		
		s2u[i] = (s2u[i - 1] + m2 + mod) % mod;
		s2u1[i] = (s2u1[i - 1] + m2 * i % mod + mod) % mod;
		s2u2[i] = (s2u2[i - 1] + m2 * i * (LL)i % mod + mod) % mod;
		
		cnt += mu[i] != 0;
	}
	//printf("cnt = %d\n", cnt);
	//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);
		/*int a1 = 0;
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(__gcd(i, j) == 1) {
					a1 += (n - i + 1) * (n - j + 1);
					if(n - 2 * i >= 0 && n - 2 * j >= 0) {
						a1 -= (n - 2 * i + 1) * (n - 2 * j + 1);
					}
				}
			}
		}
		a1 = a1 * 2 + 2 + n * 2;
		if(n == 0) a1 = 0;
		printf("%d\n", a1);
		//cout << solve(n) << '?' << solve(n / 2) << endl;
		assert(ans == a1);*/
	}
}