#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e7;
const int mo=100003;
typedef long long ll;
ll mu[10000010],mu1[maxn+10],mu2[maxn+10];
int prime[maxn+10],flag[maxn+10];
int main()
{
    mu[1]=1;
    int cnt=0;
    flag[1]=1;
    for (int i=2;i<=maxn;i++)
    {
        if (!flag[i]) prime[++cnt] = i,mu[i]=-1;
        for (int j=1;j<=cnt;j++)
        {
            if (i*prime[j] > maxn) break;
            flag[i*prime[j]] =1;
            if (i%prime[j]==0)
            {
                mu[i*prime[j]]=0;
                break;
            }
            mu[i*prime[j]] = -mu[i];
        }
    }
    for (int i=1;i<=maxn;i++)
    {
        mu1[i]=mu[i]*i%mo;
        mu2[i]=(ll)mu[i]*i*i%mo;
    }
    for (int i=2;i<=maxn;i++)
    {
        mu[i]=(mu[i-1]+mu[i]+mo)%mo;
        mu1[i]=(mu1[i-1]+mu1[i]+mo)%mo;
        mu2[i]=(mu2[i-1]+mu2[i]+mo)%mo;
    }
    int q;
    scanf("%d",&q);
    while (q--)
    {
        int n;
        scanf("%d",&n);
        if (n==1)
        {
            puts("0");
            continue;
        }
        ll ans=0;
        int r;
        for (int l=1;l<=n;l=r+1)
        {
            int now=n/l;
            r=n/now;
            ll tmp=(ll)n*n%mo*(mu[r]-mu[l-1]+mo)%mo;
            tmp=tmp*now%mo*now%mo;
            (ans+=tmp)%=mo;
            tmp=n*now%mo*now%mo*(now+1)%mo*(mu1[r]-mu1[l-1]+mo)%mo;
            ans=(ans-tmp+mo)%mo;
            tmp=(ll)now*(now+1)/2;
            tmp%=mo;
            tmp=tmp*tmp%mo;
            tmp=tmp*(mu2[r]-mu2[l-1]+mo)%mo;
            ans=(ans+tmp)%mo;
        }
        
        for (int l=1;l<=n/2;l=r+1)
        {
            int now=(n/2)/l;
            r=(n/2)/now;
            ll tmp=(ll)n*n%mo*(mu[r]-mu[l-1]+mo)%mo;
            tmp=tmp*now%mo*now%mo;
            ans=(ans-tmp+mo)%mo;
            tmp=n*now%mo*now%mo*(now+1)%mo*(mu1[r]-mu1[l-1]+mo)%mo;
            ans=(ans+tmp*2%mo+mo)%mo;
            tmp=(ll)now*(now+1)/2;
            tmp%=mo;
            tmp=tmp*tmp%mo;
            tmp=tmp*(mu2[r]-mu2[l-1]+mo)%mo;
            ans=(ans-tmp*4%mo+mo)%mo;
        }
        printf("%lld\n",((ans+n)*2)%mo);
    }
    return 0;
}