#include <fstream>
#include<vector>
#include<cmath>
#include<iostream>
using namespace std;
int prime(int n)
{
	int x=0;
	for(int i=2;i*i<=n;i++)
	{
		if(n%i==0) {x++;break;};
	}
	if(x==0) return 1;
	else return 0;
}
int main()
{
	int kt=0;
	int l;
	ifstream fi("DQPTNT.inp");
	int n;
	int r;
	fi>>l;
	ofstream fo("DQPTNT.out");
	for(int a=0;a<l;a++)
	{
		int max=0;
		fi>>n;
		if(n<0)
		{
			
		}
		if((prime(n)==1)&&(n>0))
		{
			fo<<n<<":"<<n<<endl;
		}
		if((n>0)&&(prime(n)==0)){
		kt=1;
		fo<<n<<":";
		vector <int> m(n,0);
		int p=n;
		for(int i=2;i<=n;i++)
		{
			if((n%i==0)&&(prime(i)==1))
				{

					while(n%i==0)
					{
						m[i]++;
						if(i>max)
						{
							max=i;
						}
						n=n/i;
					}
				}
		}
			for(int x=2;x<=max;x++)
			{
				if(m[x]>1)
				{
					fo<<x<<"^"<<m[x];
					r=pow(x,m[x]);
					if(p/r!=1)
					{
						fo<<"*";
					}
					p=p/r;
				}
				if(m[x]==1)
				{
					fo<<x;
					if(p/x!=1)
					{
						fo<<"*";
					}
					p=p/x;
				}
			}
			fo<<endl;
		}
	}
	if(kt==0)
	{
		fo<<"Khong co so nguyen duong nao";
	}
	fi.close();
	fo.close();
	return 0;
}
