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

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

long long summob(int l,int r){
    return (pref[r]-pref[l-1])%mod;
}

long long summobi(int l,int r){
    return (pref2[r]-pref2[l-1])%mod;
}

long long summobii(int l,int r){
    return (pref3[r]-pref3[l-1])%mod;
}

long long sum(long long n){
    return (n+1)*n/2ll%mod;
}

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

long long xtimesy(long long n){
    long long res=0;
    
    for(long long i=1;i<=n;i++){
        int last = n/(n/i);
        res+=summobii(i,last)*sum(n/i)%mod*sum(n/i)%mod;
        res%=mod;
        
        i=last;
    }
    
    return res;
}

long long coprimepair(long long n){
    long long res=0;
    
    for(int i=1;i<=n;i++){
        int last = n/(n/i);
        res+=summob(i,last)*(n/i)*(n/i)%mod;
        res%=mod;
        
        i=last;
    }
    
    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;
    pref[1]=1;
    pref2[1]=1;
    pref3[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;
        pref[i]=(pref[i-1]+mob[i])%mod;
        pref2[i]=(pref2[i-1]+mob[i]*i)%mod;
        pref3[i]=(pref3[i-1]+mob[i]*i*i)%mod;
    }
    
    int t=1;
    cin>>t;
    for(int i=1;i<=t;i++)solve();
    
    return 0;
}