#include <bits/stdc++.h>
using namespace std;
#define rep(i, l, r) for (int i = l; i <= r; ++i)
const int N = 1e7 + 5; 
const int P = 1e6 + 3; 
int n, q, r, S, t, pra, cnt, ans, res, Inv, pr[N], mu[N], pre[N];
bool ipr[N];  

int inc (int a, int b) { return (a += b) >= P ? a - P : a; }
int dec (int a, int b) { return (a -= b) < 0 ? a + P : a; }
int mul (int a, int b) { return 1ll * a * b % P; }
int fpow (int a, int b) { int ans = 1; for ( ; b; a = mul(a, a), b >>= 1) if(b & 1) ans = mul(ans, a); return ans; }
void sieve (int n) {
  ipr[1] = mu[1] = 1;
  rep(i, 2, n) {
    if(!ipr[i]) pr[++cnt] = i, mu[i] = P - 1; 
    for (int j = 1; j <= cnt && i <= n / pr[j]; ++j) {
      ipr[i * pr[j]] = 1; 
      if(i % pr[j] == 0) { mu[i * pr[j]] = 0; break ; }
      ipr[i * pr[j]] = 1, mu[i * pr[j]] = dec(0, mu[i]); 
    }
  } 
  rep(i, 1, n) pre[i] = inc(pre[i - 1], mu[i]); 
}

int main () {
  sieve(N - 5); 
  cin >> q;
  pra = mul(3, fpow(4, P - 2)); 
  Inv = fpow(2, P - 2); 
  while (q--) {
    cin >> n, ans = n; 
    // rep(i, 1, n) printf("%d ", mu[i]); printf("\n"); 
    if(n == 1) { puts("0"); continue ; }
    rep(d, 1, n) {
      int x = n / d; 
      res = mul(n, x); 
      res = dec(res, mul(d, mul(x, mul(x + 1, Inv)))); 
      res = mul(res, res); 
      ans = inc(ans, mul(mu[d], res)); 
    }
    rep(d, 1, n / 2) {
      int x = n / 2 / d; 
      res = mul(n, x); 
      res = dec(res, mul(2 * d, mul(x, mul(x + 1, Inv)))); 
      res = mul(res, res); 
      ans = dec(ans, mul(mu[d], res)); 
    }
    printf("%d\n", mul(ans, 2)); 
  }
  return 0; 
}