#include <iostream>
#include <bits/stdc++.h>
#define NM 1000005
#define pb push_back
#define m 9973
using namespace std;
ifstream in("ssnd.in");
ofstream out("ssnd.out");
int ciur[NM];
vector<long long> prim,divv;
map<long long,long long> fr,val;
long long t,n,s,nrdiv,sdiv;
int main()
{
    in>>t;
    for(int i=2;i<=1000000;++i)ciur[i]=1;
    for(long long i=2;i<=1000000;++i)
        if(ciur[i])
        {
            prim.pb(i);
            for(long long j=i*i;j<=1000000;j+=i)
                ciur[j]=0;
        }
//    while(t)
//    {
//        --t;
//        in>>n;
//        fr.clear();
//        val.clear();
//        divv.clear();
//        sdiv=1;
//        nrdiv=1;
//        for(int i=0;n>1 && prim[i]<=sqrt(n);++i)
//        {
//            if(n%prim[i]==0)divv.pb(prim[i]);
//            while(n%prim[i]==0)
//            {
//                n/=prim[i];
//                if(fr.find(prim[i])==fr.end())
//                {
//                    val[prim[i]]=prim[i];
//                    fr[prim[i]]=2;
//                }
//                else ++fr[prim[i]];
//                val[prim[i]]*=prim[i];
//            }
//        }
//        if(n>1)
//        {
//            fr[n]=2;
//            divv.pb(n);
//            val[n]=n*n;
//        }
//        for(auto i:divv)
//        {
//            nrdiv*=fr[i];
//            nrdiv%=m;
//            sdiv*=(val[i]-1)/(i-1);
//            sdiv%=m;
//        }
//        out<<nrdiv<<" "<<sdiv<<'\n';
//    }
    return 0;
}