#include <fstream>
#include <bitset>
using namespace std;
ifstream fin("ssnd.in");
ofstream fout("ssnd.out");
int cont,t,s,prim[1000010],nrprim=1;
long long n;
bitset<1000010>ciur;
int putere(int a, int b) {
    int r = 1;
    a%=9973;
    while (b!=0) {
        if (b%2==1){
            r = (r*a)%9973;
        }
        a = a*a%9973;
        b=b/2;

    }

    return r;

}


int main(){
    prim[nrprim]=2;
    for (int i=3;i<=1000000;i+=2) {
        if (ciur[i]==0){
            nrprim++;
            prim[nrprim] =i;
            for (int j=i+i;j<=1000000;j+=i){
                ciur[j]=1;
            }


        }

    }
    fin>>t;
    for(int i=1;i<=t;i++){
        fin>>n;
        cont=1;
        s=1;
        for(int i=1;n!=1 && 1LL*prim[i]*prim[i]<=n;i++){
            if(n%prim[i]==0){
                int power=0;

                while(n%prim[i]==0){
                    power++;
                    fout<<n<<"\n";

                }
                fout<<n<<" "<<prim[i]<<" "<<power<<"\n";
                long long exp=putere(prim[i],power+1);
                exp--;
                if(exp<0){
                    exp+=9973;
                }

                cont*=(power+1);
                s*=(exp/(prim[i]-1))%9973;


            }
        }
        //fout<<cont<<" "<<s<<"\n";
    }





}