#include <bits/stdc++.h>
using namespace std;
int e,b[1000];
bool test(int a)
{
	for (int i=2; i<=sqrt(a); i++)
	if (a%i==0) return false;
	return true;
}
void ptich(int a)
{
	 e=2;
	if (e<=sqrt(a))
	{
		if (a%e==0) a=a/e; else e++;
	}
}
int main ()
{
	freopen ("DQPTNT.inp","r",stdin);
	freopen ("DQPTNT.out","w",stdout);
	int n;
	cin>>n;
	int a[n+1], c;
	for (int i=1; i<=n; i++)
	cin >> a[i];
	for (int i=1; i<=n; i++)
	{	cout << a[i]<<":";
		c=a[i];
		if (a[i]<=3) cout<< a[i]; else
		{
		while (test(a[i])==false)
		{ptich(a[i]);
		b[e]++;
		}
		b[a[i]]++;
		for (int y=2; y<=a[i]; y++)
		{
			if (b[y]>0) 
			{
				if (b[y]>1&&y!=a[i]) cout << y << "^"<<b[i]<<"*";
				if (b[y]==1) cout << y<<"*";
				if (y==a[i])
				{
					if (b[y]>1) cout << y << "^"<<b[y];
					else cout << y;
				}
				b[y]=0;
			}
		}
	}
}
}
