#include <fstream>

using namespace std;

ifstream input("DQPTNT.inp");
ofstream output("DQPTNT.out");

int temp = -1;
int Count = 0;

void Factor(int a, int i = 2)
{
	if (a <= 1)
	{
		return;
	}
	if (a % i == 0)
	{
		if (temp != i)
		{
			if (Count > 0)
			{
				output << temp;
				if (Count > 1)
				{
					output << '^' << Count;
				}
				output << '*';
			}
			temp = i;
			Count = 1;
		}
		else
		{
			Count++;
		}
		Factor(a / i, i);
	}
	else
	{
		Factor(a, i + 1);
	}
}

int main()
{
	int n;
	int a;
	input >> n;
	for (int i = 0; i < n; i++)
	{
		input >> a;
		if (a > 0)
		{
			output << a << ':';
			Factor(a);

			if (Count > 0)
			{
				output << temp;
				if (Count > 1)
				{
					output << '^' << Count;
				}
			}
			output << '\n';
		}
		Count = 0;
		temp = -1;
	}
	input.close();
	output.close();
	return 0;
}