#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e7 + 9;
int phi[N];
void totient() {
  for (int i = 1; i < N; i++) phi[i] = i;
  for (int i = 2; i < N; i++) {
    if (phi[i] == i) {
      for (int j = i; j < N; j += i) phi[j] -= phi[j] / i;
    }
  }
}

int e(int n) {
    if (n % 2 == 0) return 0;
    return phi[(n - 1) / 2];
}

int R2(int n) {
    if (n % 2 == 0) return (n - 1) * phi[n-1];
    if (n % 4 == 1) return (n - 1) * phi[(n - 1) / 2];
    return 0;
}
const int mod = (int)1e6+3;
signed main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	totient();
    vector<int> L(N + 1, 0), L1(N + 1, 0), R1(N + 1, 0);
    L[0] = 0;
    L1[1] = 0;
    R1[1] = 0;
    for (int n = 2; n <= N; n++) {
        R1[n] = R1[n - 1] + 4 * (phi[n - 1] - e(n));
        L1[n] = 2 * L[n - 1] - L1[n - 1] + R2(n);
        L[n] = 2 * L1[n] - L[n - 1] + R1[n];
        R1[n]%=mod;
        L1[n]%=mod;
        L[n]%=mod;
    }
    int q;
    cin >> q;
    while(q--){
    	int x;
    	cin >> x;
    	cout << L[x] << '\n';
    }
    return 0;
}