#include <bits/stdc++.h>
using namespace std;
int stt = 1;
void pt(int n)
{
cout << "Test " << stt++ << ": ";
for (int i = 2; i<=sqrt(n); i++)
{
int dem = 0;
if (n%i==0)
{
while (n%i==0)
{
++dem;
n/=i;
}
cout << i << "(" << dem << ")" << " ";
}
}
if (n > 1) cout << n << "(1)";
cout << endl;
}
int main()
{
int t; cin >> t;
while (t--)
{
int n; cin >> n;
pt(n);
}
return 0;
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CmludCBzdHQgPSAxOwp2b2lkIHB0KGludCBuKQp7Cgljb3V0IDw8ICJUZXN0ICIgPDwgc3R0KysgPDwgIjogIjsgCglmb3IgKGludCBpID0gMjsgaTw9c3FydChuKTsgaSsrKQoJewoJCWludCBkZW0gPSAwOwoJCWlmIChuJWk9PTApCgkJewoJCQl3aGlsZSAobiVpPT0wKQoJCQl7CgkJCQkrK2RlbTsKCQkJCW4vPWk7CgkJCX0KCQkJY291dCA8PCBpIDw8ICIoIiA8PCBkZW0gPDwgIikiIDw8ICIgIjsKCQl9Cgl9CglpZiAobiA+IDEpIGNvdXQgPDwgbiA8PCAiKDEpIjsKCWNvdXQgPDwgZW5kbDsgCn0KaW50IG1haW4oKQp7CglpbnQgdDsgY2luID4+IHQ7IAoJd2hpbGUgKHQtLSkKCXsKCQlpbnQgbjsgY2luID4+IG47IAoJCXB0KG4pOwoJfQoJcmV0dXJuIDA7Cn0=