#include <bits/stdc++.h>

using namespace std;

const int NMAX = 10000000;
const int MOD = 1000003;

int is_composite[NMAX + 5];
int mobius[NMAX + 5];
int mobius_times_d[NMAX + 5]; 

int add(int a, int b){
  a += b;
  if(a >= MOD){
    a -= MOD;
  }
  return a;
}

int sub(int a, int b){
  a -= b;
  if(a < 0){
    a += MOD;
  }
  return a;
}

int mult(int a, int b){
  return 1LL * a * b % MOD;
}

int main(){

  for(int i = 1;i <= NMAX;i++){
    mobius[i] = 1;
    is_composite[i] = false;
  }

  for(int i = 2;i <= NMAX;i++){
    if(is_composite[i]){
      continue;
    }
    for(int j = i;j <= NMAX;j += i){
      mobius[j] *= -1;
    }
    if(1LL * i * i <= NMAX){
      for(int j = i * i; j <= NMAX;j += i * i){
        mobius[j] = 0;
      }
    }
  }

  for(int i = 1;i <= NMAX;i++){
    if(mobius[i] < 0){
      mobius[i] = MOD + mobius[i];
    }
    mobius_times_d[i] = mult(i, mobius[i]);
    mobius[i] = add(mobius[i - 1], mobius[i]);
    mobius_times_d[i] = add(mobius_times_d[i - 1], mobius_times_d[i]);
  }
  
  int q;
  scanf("%d", &q);

  while(q--){
    int n;
    scanf("%d", &n);

    if(n == 1){
      printf("%d\n", 0);
      continue;
    }

    vector<pair<int, int> > ranges;

    int max_d = 0;
    for(int d = 1; 1LL * d * d < n;d++){
      // trb sa bagam
      ranges.push_back({d, d});
      max_d = d;
    }
    for(int d = 1; 1LL * d * d < n;d++){
      ranges.push_back({(n - 1)  / (d + 1) + 1, (n - 1) / d});
      if(ranges.back().first <= max_d){
        ranges.back().first = max_d + 1;
        if(ranges.back().second < ranges.back().first){
          ranges.pop_back();
          break;
        }
      }
    }

    int first_sum = 0;
    int second_sum = 0;

    for(auto it:ranges){
      int value = ((n - 1) / it.first) % MOD;
      first_sum = add(first_sum, mult(mult(value, value), sub(mobius[it.second], mobius[it.first - 1])));
      second_sum = add(second_sum, mult(mult(mult(value, value),mult(add(value, 1), MOD / 2 + 1)), sub(mobius_times_d[it.second], mobius_times_d[it.first - 1])));
    }

    //cerr << "debug " << first_sum << " " << second_sum << "\n";
    printf("%d\n", add(sub(mult(sub(mult(4, n), 2), first_sum), mult(4, second_sum)), add(n, n)));
  }

  return 0;
}