#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
const int mod=1000003,N=10000010;
int p[N/10],mu[N],pt,s0[N],s1[N],s2[N];bool pr[N];
void posi(int &x){x=x<0?x+mod:x;}
void init(int n=N-10)
{
    mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!pr[i]) p[++pt]=i,mu[i]=-1;
        for(int j=1;j<=pt && i*p[j]<=n;j++)
        {
            pr[i*p[j]]=true;
            if(i%p[j]==0){mu[i*p[j]]=0;break;}
            else mu[i*p[j]]=-mu[i];
        }
    }
    for(int i=1;i<=n;i++)
    {
        s0[i]=(s0[i-1]+mu[i])%mod;
        s1[i]=(s1[i-1]+i*mu[i])%mod;
        s2[i]=(s2[i-1]+1ll*i*i*mu[i])%mod;
        posi(s0[i]),posi(s1[i]),posi(s2[i]);
    }
}
int calc(int x){return 1ll*x*(x+1)/2;}
int solve0(int n,int m)
{
    int ans=0;
    if(n>m) swap(n,m);
    for(int l=1,r;l<=n;l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        ans=(ans+1ll*(n/l)*(m/l)%mod*(s0[r]-s0[l-1]))%mod;
    }
    return ans;
}
int solve1(int n,int m)
{
    int ans=0;
    if(n>m) swap(n,m);
    for(int l=1,r;l<=n;l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        ans=(ans+1ll*(1ll*(m/l)*calc(n/l)+1ll*(n/l)*calc(m/l))%mod*(s1[r]-s1[l-1]))%mod;
    }
    return ans;
}
int solve2(int n,int m)
{
    int ans=0;
    if(n>m) swap(n,m);
    for(int l=1,r;l<=n;l=r+1)
    {
        r=min(n/(n/l),m/(m/l));
        ans=(ans+1ll*calc(n/l)*calc(m/l)%mod*(s2[r]-s2[l-1]))%mod;
    }
    return ans;
}
int brute(int n)
{
    int ans=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            for(int x=1;i+x<=n;x++)
                for(int y=1;j+y<=n;y++) if(__gcd(x,y)==1)
                {
                    if(i-x>=1 && j-y>=1) continue;
                    ++ans;
                }
        }
    // for(int i=1;i<=n;i++)
    //     for(int j=1;j<=n;j++) if(__gcd(i,j)==1)
    //     {
    //         if(i<=n/2 && j<=n/2) ans=(ans+(i+j)*n-3*i*j)%mod;
    //         else ans=(ans+(n-i)*(n-j))%mod;
    //     }
    posi(ans);
    return ans*2%mod;
}
int part1(int n)
{
    int r1=n*solve1(n/2,n/2)%mod;
    int r2=3ll*solve2(n/2,n/2)%mod;
    return (r1-r2+mod)*2ll%mod;
}
int subcalc(int n0,int n,int m)
{
    return (1ll*n0*n0%mod*solve0(n,m)-1ll*n0*solve1(n,m)%mod+solve2(n,m)%mod+mod)%mod;
}
int part2(int n)
{
    int r1=subcalc(n,n/2,n/2);
    int r2=subcalc(n,n,n);
    return (r2-r1+mod)*2ll%mod;
}
signed main()
{
    init();
    int T;scanf("%lld",&T);
    while(T --> 0)
    {
        int n;scanf("%lld",&n);
        if(n==1){puts("0");continue;}
        // int res=brute(n);
        int res2=(part1(n)+part2(n))%mod;
        posi(res2);
        // printf("%d\n",(res+2*n)%mod);
        printf("%lld\n",(res2+2*n)%mod);
    }
    return 0;
}