#include <iostream>
#include <stdio.h>
#define dokle 1234567

using namespace std;

char buff[dokle], *pozicija=buff+dokle;
inline char ucitaj_sledeci()
{
    if(pozicija==buff+dokle)
    {
        fread(buff,1,dokle,stdin);
        pozicija=buff;
    }
    return *pozicija++;
}
inline void ispisi_char(char c)
{
    fwrite(&c,1,sizeof(c),stdout);
}
inline int ucitaj_int()
{
    int broj=0;
    char c;
    while((c=ucitaj_sledeci())<'0' || c>'9');
    do
    {
        broj=broj*10+(c-'0');
    }while((c=ucitaj_sledeci())>='0' && c<='9');
    return broj;
}
inline char ucitaj_char()
{
    char c;
    while( (c=ucitaj_sledeci())<'a' || c>'z' )
    return c;
}
inline void ispisi_int(int n)
{
        int cifre[10],brcifre;
        if(n==0)
        {
            ispisi_char('0');
            ispisi_char('\n');
            return;
        }
        for(brcifre=0; n; brcifre++)
        {
            cifre[brcifre]=n%10;
            n/=10;
        }
        for(;brcifre;brcifre--) ispisi_char(cifre[brcifre-1]+'0');
        ispisi_char('\n');
}



                    //         ZADATAK:
bool composite[200000] ;
int izlozilac[200000] , flag;
int  n, x ;

void eratosten();




int main ()
{

    eratosten();

    n=ucitaj_int();

    for( int l=0; l<n; ++l ) {


    scanf("%d", &x);

    if( composite[x] == false ) { printf("%d^1\n", x ); continue; }


    for( int i=2; i<200000 && x!=1; ++i ) {

        if( !composite[i] &&  x%i == 0 ){

            if( i>x ) { break; }

            while( x%i == 0 ) { izlozilac[i]++; x/=i; }
        }

        if( izlozilac[i]>0 && !flag ) { printf("%d^%d", i, izlozilac[i]); flag= true; izlozilac[i]=0; }
        else if( izlozilac[i]>0 && flag){ printf("*%d^%d", i, izlozilac[i]); izlozilac[i]=0; }
        if( composite[x] == false && x!=1 ){ cout<<"*"<<x<<"^1"; break; }
    }
    flag=0;
    printf("\n");

    }

    return 0;
}

void eratosten()
{

    for (int i = 2; i <= 448; i++)
    {

        if (!composite[i])
        {

            for (int j = i; i * j <= 200000; j++)
            {
                if (composite[i * j] == 0)
                {
                    composite[i * j] = true;
                }
            }
        }
    }
}