#include <bits/stdc++.h>
const int N = 1e7 + 5, MOD = 1e6 + 3;
int mu[N], s_sq[N], s[N], s_0[N], p[N], p_cnt;
bool flag[N];
void Init() {
mu[1] = 1;
for(int i = 2; i < N; ++i) {
if(!flag[i]) { p[++p_cnt] = i; mu[i] = -1; }
for(int j = 1; j <= p_cnt && i * p[j] < N; ++j) {
flag[i * p[j]] = true;
if(i % p[j] == 0) { mu[i * p[j]] = 0; break; }
mu[i * p[j]] = -mu[i];
}
}
for(int i = 1; i < N; ++i) {
s_0[i] = (s_0[i - 1] + mu[i] + MOD) % MOD;
s[i] = (s[i - 1] + 1LL * mu[i] * i + MOD) % MOD;
s_sq[i] = (s_sq[i - 1] + 1LL * mu[i] * i * i + MOD) % MOD;
}
}
int S(int x) { return 1LL * x * (x - 1) / 2 % MOD; }
int Sq(int x) { return 1LL * x * x % MOD; }
int Solve0(int n, int tar = N) {
int ret = 0;
n = tar = std::min(n, tar);
for(int l = 1, r; l <= n && l <= tar; l = r + 1) {
r = std::min(n / (n / l), tar);
ret = (ret + 1LL * (s_0[r] - s_0[l - 1]) * Sq(tar / l)) % MOD;
}
ret = (ret + MOD) % MOD;
return ret;
}
int Solve1(int n, int tar = N) {
int ret = 0; //tar = std::min(n, tar);
n = tar = std::min(n, tar);
for(int l = 1, r; l <= n && l <= tar; l = r + 1) {
r = std::min(n / (n / l), tar);
ret = (ret + 1LL * (s[r] - s[l - 1]) * S(tar / l) % MOD * (tar / l)) % MOD;
}
ret = (ret + MOD) % MOD;
return ret;
}
int Solve2(int n, int tar = N) {
int ret = 0;
n = tar = std::min(n, tar);
for(int l = 1, r; l <= n && l <= tar; l = r + 1) {
r = std::min(n / (n / l), tar);
ret = (ret + 1LL * (s_sq[r] - s_sq[l - 1]) * Sq(S(tar / l))) % MOD;
}
ret = (ret + MOD) % MOD;
return ret;
}
int Gcd(int a, int b) { return b ? Gcd(b, a % b) : a; }
int main() {
int q; Init();
//Test(10);
scanf("%d", &q);
while(q--) {
int n; scanf("%d", &n);
/*int ans = (-Solve1(n) + 2LL * Solve2(n) * n) % MOD;
ans = (ans + MOD) % MOD;*/
int ans = 0;
/*for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j) if(Gcd(i, j) == 1) {
int v;
if(i >= (n + 1) / 2 || j >= (n + 1) / 2) {
v = (n - i) * (n - j);
//printf("A %d %d %d\n", i, j, v);
} else {
v = (n - i) * j + (n - j) * i - i * j;
//printf("B %d %d %d\n", i, j, v);
}
ans += v;
}
printf("\n");*/
/*for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j)
if(Gcd(i, j) == 1) ans += i;
printf("%d %d\n", ans, Solve1(n, n));*/
ans = (2LL * n * n % MOD * Solve0(n, n / 2) % MOD - 3LL * Solve2(n, n / 2)) % MOD;
ans = (ans + 1LL * n * n % MOD * Solve0(n) % MOD - Solve2(n) + 2LL * n * Solve1(n)) % MOD;
ans = (ans - (1LL * n * n % MOD * Solve0(n, n / 2) % MOD - Solve2(n, n / 2) + 2LL * n * Solve1(n, n / 2))) % MOD;
ans = (ans + MOD) % MOD;
printf("%d\n", (ans * 2 + 2 * n) % MOD);
}
return 0;
}