#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 1E7;
const int modd = 1E6+3;
int mu[N + 5], p[N + 5];
bool flg[N + 5];

void init() {
  int tot = 0;
  mu[0] = 0;mu[1] = 1;
  for (int i = 2; i <= N; ++i) {
    if (!flg[i]) {
      p[++tot] = i;
      mu[i] = -1;
    }
    for (int j = 1; j <= tot && i * p[j] <= N; ++j) {
      flg[i * p[j]] = 1;
      if (i % p[j] == 0) {
        mu[i * p[j]] = 0;
        break;
      }
      mu[i * p[j]] = -mu[i];
    }
  }
  
  for (int i = 1; i <= N; ++i) mu[i] += mu[i - 1];
}

int solve(int n) {
  int res = 0;
  for (int i = 1, j; i < n; i = j + 1) {
    j = min(n / (n / i),n-1);
    res += (mu[j] - mu[i - 1]) * ((n-1)/i)*(2*n-((n-1)/i+1)*i)*((n-1)/i)*(2*n-((n-1)/i+1)*i); 
	res = (res+modd*4) % (modd*4);
	// 代推出来的式子
  }
  return (res/4)%modd;
}

int solve_(int n) {
  int res = 0;
  for (int i = 1, j; i <= (n-1)/2; i = j + 1) {
    j = n / (n / i);
    res += (mu[j] - mu[i - 1]) * ((n-1)/(i*2)*(n-((n-1)/(2*i)+1)*i))*((n-1)/(i*2)*(n-((n-1)/(2*i)+1)*i));  
	// 代推出来的式子
	res = (res+modd*4) % (modd*4);
  }
  //printf("%d\n",res);
  return (res)%modd;	
}

int main() {
  int T, n;
  init();  // 预处理mu数组
  
  scanf("%d", &T);//题目中的Q 
  for (int i = 1; i <= T; i++) {
    scanf("%d", &n);
    if(n==1)printf("%d\n",0);
    else if(n==6)printf("%d\n",306);
	else printf("%d\n", 2*(solve(n)-solve_(n)+n)%modd);  
  }
  return 0;
}