#include <bits/stdc++.h>
#define cs const
#define pb push_back
using namespace std;
using ll = long long ; 
cs int N = 1e7 + 5; 
cs int mod = 1e6 + 3; 
int Q;
vector <int> prm; 
bool ex[N];
int phi[N];
int s1[N], s2[N], s3[N];
void Add(int &x, int y) {
    x += y;
    x = x % mod; 
}
void Dec(int &x, int y) {
    y = y % mod; 
    x = x % mod; 
    x = (x - y + mod) % mod; 
}
void init(int n) {
    phi[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(!ex[i]) prm.pb(i), phi[i] = i - 1; 
        for(int x : prm) {
            if(x * i > n) break;
            ex[x * i] = 1; 
            if(i % x == 0) {
                phi[i * x] = phi[i] * x; 
                break;
            }
            phi[i * x] = phi[i] * (x - 1);
        }
    }
    for(int i = 1; i <= n; i++) {
        s1[i] = phi[i] % mod; 
        Add(s1[i], s1[i - 1]);
        s2[i] = (1ll * i * phi[i] + 1ll * i * phi[i] / 2) % mod;  
        Add(s2[i], s2[i - 1]);
        s3[i] = (1ll * i * phi[i] / 2) % mod * i % mod;
        Add(s3[i], s3[i - 1]);
    }
}
int S1(int n) {
    return (2ll * s1[n] - 1 + mod) % mod;
}
int S2(int n) {
    return (2ll * s3[n] + 1) % mod; 
}
int S3(int n) {
    return (2ll * s2[n]) % mod; 
}
int main() {
    #ifdef zqj
    freopen("1.in","r",stdin);
    #endif
    cin >> Q; 
    init(1e7);
    for(int i = 1; i <= Q; i++) {
        int n; 
        scanf("%d", &n);
        if(n == 1) {
            cout << 0 << '\n';
            continue; 
        }
        int ans = 1ll * n * n % mod * S1(n - 1) % mod; 
        Add(ans, S2(n - 1));
        Dec(ans, n * S3(n - 1) % mod);
        
        Dec(ans, 1ll * n * n % mod * S1((n - 1) / 2) % mod); 
        Dec(ans, 4ll * S2((n - 1) / 2) % mod);
        Add(ans, 2ll * n * S3((n - 1) / 2) % mod); 
        ans = 2ll * (ans + n) % mod; 
        cout << ans << '\n';
    }
    return 0;
}