#include <bits/stdc++.h>
using namespace std;
ifstream fi("dqptnt.inp");
ofstream fo("dqptnt.out");
int somu(int n, int i){
    if (n%i==0)
    {
        return 1+somu(n/i,i);
    }
    else {return 0;}
}
void unt(int n, int i, int t, int m)
{
    if (n>=i)
    {
        if (n%i==0&&t==0){fo<<i;t++;}
        else if (n%i==0&&m==0){fo<<'*'<<i;m++;}
        if (n%i==0)
        {
            int k=somu(n,i);
            if (k>1){fo<<'^'<<k;}
            n=n/pow(i,k);
            unt(n,i,t,m);
        }
        else
        {
            unt(n,i+1,t,0);
        }
    }
}

int main()
{
    int n;
    fi>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        fi>>a[i];
        if(a[i]>1)
        {
            fo<<a[i]<<':';
            unt(a[i],2,0,0);
            fo<<endl;
        }
    }
}
