#include<iostream>
#include<vector>
#include<cmath>
#include<set>
#include<algorithm>

int main()
{
    std::vector<long long> result;
    std::vector<long long> tab(10000006, 1);
    std::vector<long long> t(10000006, 1);
    std::vector<long long> w;
    std::vector<long long> v;
    long long n;
    long long a;
    long long m;
    long long dzielnik;
    long long pierw;
    long long x;
    std::cin>>n;
    for(long long j=0; j<n; ++j)
    {

        v.clear();
        std::cin>>m;
        dzielnik=2;
        pierw=sqrt(m);
        while(m>1&&dzielnik<=pierw)
        {
            while(m%dzielnik==0)
            {
                v.push_back(dzielnik);
                m/=dzielnik;
            }
            ++dzielnik;
        }
        if(m>1)
        {
            v.push_back(m);
        }

        x=v.size();
        int iloczyn=1;
        int wynik=2;

        for(long long i=1; i<x; i++)
        {
           if(v[i]==v[i-1])
           {
               wynik++;
               t[v[i]]++;
               tab[v[i]]++;


               if(i==x-1)
               {
                    iloczyn=iloczyn*wynik;
               }

           }
           else
           {
               iloczyn=iloczyn*wynik;
                wynik=2;

               if(i==x-1)
               {
                   iloczyn=iloczyn*wynik;
               }
           }
        }
        for(int i=1; i<x; i++)
        {
            if(i==1) w.push_back(v[i]);
            if(v[i]!=v[i-1])  w.push_back(v[i]);
        }
        int y;
        y=w.size();
        int it;
        it=y-1;
        //for(int i=0; i<y; i++) std::cout<<w[i];
        //std::cout<<std::endl<<t[2]<<" "<<t[3]<<" "<<t[7];
    int dziel=1;

        for(int i=0; i<iloczyn; i++)
        {
            dziel=1;
            for(int q=0; q<y; q++)
            {
                dziel*=std::pow(w[q], t[w[q]]);



            }
            result.push_back(dziel);
            for(int q=it; q>=0; q--)
            {
                t[w[q]]--;
                if(t[w[q]]!=-1) break;
                else  t[w[q]]=tab[w[q]];


            }



        }
        std::sort(result.rbegin(), result.rend());
        int en=result.size();
        for( long long i=0; i<en; i++) std::cout<<result[i]<<std::endl;

        //////////////////////////////////////////////////////////////////////////////



        using XD = std::decay_t<decltype(*v.begin())>;
		for (long long i = 0; i < en-1; i++) //std::cout<<v[i]<<std::endl;
		{
			if (v[i] + 1 == v[i + 1])
			{
				w.push_back(v[i]);  //szukam ciagow dzielnikow
				if (v[i + 1] + 1 != v[i + 2]) w.push_back(v[i + 1]);


			}
			else if (std::accumulate(std::begin(w), std::end(w), 1, std::lcm<XD, XD>) == m)

			{
				y = w.size();
				for (long long i = 0; i < y; i++) std::cout << w[i];
				break;
			}

			else w.clear();



		}










    }

}