#include <bits/stdc++.h>
using namespace std;
ifstream f1("DQPTNT.inp");
ofstream f2("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){f2<<i;t++;}
    else if (n%i==0&&m==0){f2<<'*'<<i;m++;}
    if (n%i==0){int k=somu(n,i);
        if (k>1) {f2<<'^'<<k;}
        n=n/pow(i,k);
        unt(n,i,t,m);
    }
    else {
        unt(n,i+1,t,0);
    }
  }
}
int main(){
    int n;
    int a[n];
    f1>>n;
    for(int i=0;i<n;i++)
    {
        f1>>a[i];
        if(a[i]>0)
        {
            f2<<a[i]<<':';
            unt(a[i],2,0,0);
            f2<<endl;
        }
    }
}
