#include "bits/stdc++.h"

using namespace std;

const int N = (int) 1e7 + 22, mod = (int) 1e6 + 3;
int L[N], L1[N], R1[N], R2[N], e[N], phi[N];

int get(int n) {
    return phi[n];
}

void upd(int& x) {
    x = (x % mod + mod) % mod;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    iota(phi, phi + N, 0);
    for (int i = 1; i < N; i++) {
        for (int j = i + i; j < N; j += i) {
            phi[j] -= phi[i];
        }
    }
    for (int n = 1; n < N; n++) {
        e[n] = (n % 2 == 0 ? 0 : get((n - 1) / 2));
        upd(e[n]);
        if (n > 1) R1[n] = R1[n - 1] + 4 * (get(n - 1) - e[n]);
        upd(R1[n]);
        R2[n] = (n % 2 == 0 ? (n - 1) * get(n - 1) : (n % 4 == 1 ? (n - 1) * get(n - 1) / 2 : 0));
        upd(R2[n]);
        if (n > 1) L1[n] = 2 * L[n - 1] - L1[n - 1] + R2[n];
        upd(L1[n]);
        L[n] = 2 * L1[n] - L[n - 1] + R1[n];
        upd(L[n]);
    }
    int q;
    cin >> q;
    while (q--) {
        int n;
        cin >> n;
        cout << L[n] << '\n';
    }
}