#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e7+5;
const long long mod = 1e6+3;
int mob[MAXN];

long long sum(long long x,long long n){
    long long num = n/x;
    return (num*x+x)*num/2ll;
}

long long xplusy(long long n){
    long long res=0;
    
    for(long long i=1;i<=n;i++){
        res+=2ll*mob[i]*sum(i,n)%mod*(n/i)%mod;
        res%=mod;
    }
    
    return res;
}

long long xtimesy(long long n){
    long long res=0;
    
    for(long long i=1;i<=n;i++){
        res+=mob[i]*sum(i,n)%mod*sum(i,n)%mod;
        res%=mod;
    }
    
    return res;
}

long long coprimepair(long long n){
    long long res=0;
    
    for(int i=1;i<=n;i++){
        res+=mob[i]*(n/i)*(n/i)%mod;
        res%=mod;
    }
    
    return res;
}

long long f(long long n){
    return (n*xplusy(n/2)%mod)-(3ll*xtimesy(n/2)%mod);
}

long long g(long long n,long long num){
    return (n*n%mod*coprimepair(num)%mod)-(n*xplusy(num)%mod)+xtimesy(num);
}

void solve(){
    long long n;
    cin>>n;
    
    long long ans=0;
    
    if(n>1)ans+=n;
    ans+=f(n);
    ans+=g(n,n-1);
    ans-=g(n,n/2);
    ans*=2;
    
    ans%=mod;
    ans+=mod;
    ans%=mod;
    
    cout<<ans<<"\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    mob[1]=1;
    for(int i=2;i<MAXN;i++){
        int val = -1-mob[i];
        for(int j=2*i;j<MAXN;j+=i)mob[j]+=val;
        mob[i]=val;
    }
    
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)solve();
    
    return 0;
}