#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <sstream>
#include <cmath>
using namespace std;
int N=65537;
vector<bool> a(N,false);
vector<int> prime;
 
string getPrint(const map<int,int> &v){
	string s;
	stringstream ss;
	for(auto p: v)
		if(p.second==1)	ss<<p.first<<'*';
		else	ss<<'('<<p.first<<'^'<<p.second<<')'<<'*';
	ss>>s;
	s.pop_back();
	return s;
}
 
map<int,int> primeFactorization(unsigned int n){
	map<int,int> v;
	int i=0;
	int c=0;
	int l=prime.size();
	int p;
	int s = sqrt(n);
	while(n>1){
		while(i<l&&prime[i]<=s&&n%prime[i])	i++;
		if(i==l||prime[i]>s)	p = n;
		else	p = prime[i];
		c=0;
		while(n%p==0){
			n /= p;
			c++;
		}
		v[p] = c;
		s = sqrt(n);
	}
	return v;
}
 
void initializePrimes(){
	int m, n=N;
	a[0]=a[1]=true;
	for(int i=0; i<=sqrt(n); i++){
		if(a[i])	continue;
		prime.push_back(i);
		m = i*i;
		while(m<n){
			a[m]=true;
			m += i;
		}
	}
	for(int i=sqrt(n); i<n; i++)
		if(!a[i])	prime.push_back(i);
 
	cout<<"Prime size is "<<prime.size()<<endl;
}
 
int main() {
	initializePrimes();
	int t,n;
	cin>>t;
	while(t--){
		cin>>n;
		cout<<n<<" = "<<getPrint(primeFactorization(n))<<endl;
	}
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8c3N0cmVhbT4KI2luY2x1ZGUgPGNtYXRoPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwppbnQgTj02NTUzNzsKdmVjdG9yPGJvb2w+IGEoTixmYWxzZSk7CnZlY3RvcjxpbnQ+IHByaW1lOwoKc3RyaW5nIGdldFByaW50KGNvbnN0IG1hcDxpbnQsaW50PiAmdil7CglzdHJpbmcgczsKCXN0cmluZ3N0cmVhbSBzczsKCWZvcihhdXRvIHA6IHYpCgkJaWYocC5zZWNvbmQ9PTEpCXNzPDxwLmZpcnN0PDwnKic7CgkJZWxzZQlzczw8JygnPDxwLmZpcnN0PDwnXic8PHAuc2Vjb25kPDwnKSc8PCcqJzsKCXNzPj5zOwoJcy5wb3BfYmFjaygpOwoJcmV0dXJuIHM7Cn0KCm1hcDxpbnQsaW50PiBwcmltZUZhY3Rvcml6YXRpb24odW5zaWduZWQgaW50IG4pewoJbWFwPGludCxpbnQ+IHY7CglpbnQgaT0wOwoJaW50IGM9MDsKCWludCBsPXByaW1lLnNpemUoKTsKCWludCBwOwoJaW50IHMgPSBzcXJ0KG4pOwoJd2hpbGUobj4xKXsKCQl3aGlsZShpPGwmJnByaW1lW2ldPD1zJiZuJXByaW1lW2ldKQlpKys7CgkJaWYoaT09bHx8cHJpbWVbaV0+cykJcCA9IG47CgkJZWxzZQlwID0gcHJpbWVbaV07CgkJYz0wOwoJCXdoaWxlKG4lcD09MCl7CgkJCW4gLz0gcDsKCQkJYysrOwoJCX0KCQl2W3BdID0gYzsKCQlzID0gc3FydChuKTsKCX0KCXJldHVybiB2Owp9Cgp2b2lkIGluaXRpYWxpemVQcmltZXMoKXsKCWludCBtLCBuPU47CglhWzBdPWFbMV09dHJ1ZTsKCWZvcihpbnQgaT0wOyBpPD1zcXJ0KG4pOyBpKyspewoJCWlmKGFbaV0pCWNvbnRpbnVlOwoJCXByaW1lLnB1c2hfYmFjayhpKTsKCQltID0gaSppOwoJCXdoaWxlKG08bil7CgkJCWFbbV09dHJ1ZTsKCQkJbSArPSBpOwoJCX0KCX0KCWZvcihpbnQgaT1zcXJ0KG4pOyBpPG47IGkrKykKCQlpZighYVtpXSkJcHJpbWUucHVzaF9iYWNrKGkpOwoJCgljb3V0PDwiUHJpbWUgc2l6ZSBpcyAiPDxwcmltZS5zaXplKCk8PGVuZGw7Cn0KCmludCBtYWluKCkgewoJaW5pdGlhbGl6ZVByaW1lcygpOwoJaW50IHQsbjsKCWNpbj4+dDsKCXdoaWxlKHQtLSl7CgkJY2luPj5uOwoJCWNvdXQ8PG48PCIgPSAiPDxnZXRQcmludChwcmltZUZhY3Rvcml6YXRpb24obikpPDxlbmRsOwoJfQoJcmV0dXJuIDA7Cn0=

MTgKOSAxMAoxMDAgMTcKMjIwIDcwCjE3IDE5CjQgMTgKMzIgMjAKMTAwIDMyCjIyNCAzODUKMzAwMDA4IDMwMDAwOQ==

18
9 10
100 17
220 70
17 19
4 18
32 20
100 32
224 385
300008 300009