#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) {
    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 + 1) * phi[i] + 1ll * i * phi[i] / 2) % mod + mod) % mod;  
        Add(s2[i], s2[i - 1]);
    }
}
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 = 2ll * n * s1[n - 1] % mod; 
        Dec(ans, s2[n - 1] + 1);
        Add(ans, ans);
        Dec(ans, 2 * n - 3);
        Add(ans, n);
        Add(ans, ans);
        cout << ans << '\n';
    }
    return 0;
}