#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1E7;
constexpr int P = 1000003;

bool isprime[N + 1];
int phi[N + 1], nphi[N + 1], n2phi[N + 1];
std::vector<int> primes;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::fill(isprime + 2, isprime + N + 1, true);
    phi[1] = 1;
    for (int i = 2; i <= N; i++) {
        if (isprime[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        for (auto p : primes) {
            if (i * p > N) {
                break;
            }
            isprime[i * p] = false;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p;
                break;
            }
            phi[i * p] = phi[i] * (p - 1);
        }
    }

    for (int i = 1; i <= N; i++) {
        nphi[i] = 1LL * i * phi[i] % P;
        n2phi[i] = 1LL * i * nphi[i] % P;
    }
    for (int i = 1; i <= N; i++) {
        phi[i] = (phi[i - 1] + phi[i]) % P;
        nphi[i] = (nphi[i - 1] + nphi[i]) % P;
        n2phi[i] = (n2phi[i - 1] + n2phi[i]) % P;
    }

    int Q;
    std::cin >> Q;

    while (Q--) {
        int n;
        std::cin >> n;

        int ans = (1LL * (2 * n) * n % P * phi[n - 1] - (3LL * n) * nphi[n - 1] + n2phi[n - 1]) % P * 2 % P;
        int m = (n - 1) / 2;
        ans = (ans - 1LL * 4 * (1LL * n * (n) % P * phi[m] - 1LL * (3 * n) * nphi[m] + 1LL * 2 * n2phi[m])) % P;
      
        if (ans < 0) {
            ans += P;
        }
        std::cout << ans << "\n";
    }

    return 0;
}