#include <fstream>
#include <cmath>

using namespace std;
int n, d, s, fr[1000003], v[10000];
int main()
{
    ifstream fin("ssnd.in");
    ofstream fout("ssnd.out");
    for(i=2;i<=1000000;i++){
        if(fr[i]==0){
            for(j=i+i;j<=1000000;j+=i)
                fr[j]=1;
            v[++k]=i;
        }
    }


    nrdiv=1;
    fin>>t;
    for(i=1;i<=t;i++){
        fin>>n;
        x=n;
        t=1;
        while(v[t]<=sqrt(n)){
            nr=0;
            while(x%v[t]==0){
                nr++;
                x /= v[t];
            }
            nrdiv *= (nr+1);
            if(nr!=0){
                a=v[t];
                b=nr+1;
                p=1;
                while(b!=0){
                    if(b%2==1)
                        p *= a%9973;
                    a *= a%9973;
                    b /= 2;
                }
                p %= 9973;
                if(p>=1)
                    rest=p-1;
                else
                    rest=9972;
                b=v[t]-1;
                 while(b!=0){
                    if(b%2==1)
                        im=im*n%p;
                    n=n*n%p;
                    b=b/2;
                }
            }
        }

    }
    return 0;
}