#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],i;
 for (i=0;i<n;i++){
    fi>>a[i];
    if (a[i]>1){
        fo<<a[i]<<':';
        unt(a[i],2,0,0);
        fo<<endl;
    }
 }


}
