#include <iostream>
#include <bits/stdc++.h>
#define INFILE "cntper.in"
#define OUTFILE "cntper.out"
using namespace std;
ifstream in(INFILE);
ofstream out(OUTFILE);
int T;
vector<int> Ns;
int Nmx;
const int lAlf='z'-'a'+1;
const int NMAX=1000010;
const int MOD=666013;
array<int,NMAX> putere;
array<int,NMAX> num;
array<int,NMAX> desc;
void CalcPutere(int N){
    int pr=1;
    putere[0]=pr;
    for(int i=1;i<=N;i++){
        pr*=lAlf;
        pr=pr%MOD;
        putere[i]=pr;
    }
}

void Read(){
    in>>T;
    for(int i=0;i<T;i++){
        int n;
        in>>n;
        Nmx=max(Nmx,n);
        Ns.push_back(n);
    }
    CalcPutere(Nmx);
}
void Determinare(){
    for(int i=1;i<=Nmx;i++){
        num[i]=(num[i]+putere[i])%MOD;
        for(int j=2*i;j<=Nmx;j+=i){
            num[j]-=num[i];
            if(num[j]<0)
                num[j]+=MOD;
        }
    }
}
void Afisare(){
    for(auto N:Ns){
        out<<num[N]<<"\n";
    }
}
int main()
{
    Read();
    Determinare();
    Afisare();
    return 0;
}