#include <iostream>
#include <map>
using namespace std;
void primeFactorization(int test_case, int n) {
map<int, int> factors;
// Phân tích n thành thừa số nguyên tố
for (int i = 2; i * i <= n; i++) {
while (n % i == 0) {
factors[i]++;
n /= i;
}
}
// Nếu n vẫn còn lớn hơn 1, thì nó là một số nguyên tố
if (n > 1) {
factors[n]++;
}
// In kết quả
cout << "Test " << test_case << ": ";
for (auto it = factors.begin(); it != factors.end(); ++it) {
cout << it->first << "(" << it->second << ") ";
}
cout << endl;
}
int main() {
int t;
cin >> t;
for (int i = 1; i <= t; i++) {
int n;
cin >> n;
primeFactorization(i, n);
}
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8bWFwPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdm9pZCBwcmltZUZhY3Rvcml6YXRpb24oaW50IHRlc3RfY2FzZSwgaW50IG4pIHsKICAgIG1hcDxpbnQsIGludD4gZmFjdG9yczsKICAgIAogICAgLy8gUGjDom4gdMOtY2ggbiB0aMOgbmggdGjhu6thIHPhu5Egbmd1ecOqbiB04buRCiAgICBmb3IgKGludCBpID0gMjsgaSAqIGkgPD0gbjsgaSsrKSB7CiAgICAgICAgd2hpbGUgKG4gJSBpID09IDApIHsKICAgICAgICAgICAgZmFjdG9yc1tpXSsrOwogICAgICAgICAgICBuIC89IGk7CiAgICAgICAgfQogICAgfQogICAgCiAgICAvLyBO4bq/dSBuIHbhuqtuIGPDsm4gbOG7m24gaMahbiAxLCB0aMOsIG7DsyBsw6AgbeG7mXQgc+G7kSBuZ3V5w6puIHThu5EKICAgIGlmIChuID4gMSkgewogICAgICAgIGZhY3RvcnNbbl0rKzsKICAgIH0KICAgIAogICAgLy8gSW4ga+G6v3QgcXXhuqMKICAgIGNvdXQgPDwgIlRlc3QgIiA8PCB0ZXN0X2Nhc2UgPDwgIjogIjsKICAgIGZvciAoYXV0byBpdCA9IGZhY3RvcnMuYmVnaW4oKTsgaXQgIT0gZmFjdG9ycy5lbmQoKTsgKytpdCkgewogICAgICAgIGNvdXQgPDwgaXQtPmZpcnN0IDw8ICIoIiA8PCBpdC0+c2Vjb25kIDw8ICIpICI7CiAgICB9CiAgICBjb3V0IDw8IGVuZGw7Cn0KCmludCBtYWluKCkgewogICAgaW50IHQ7CiAgICBjaW4gPj4gdDsKICAgIAogICAgZm9yIChpbnQgaSA9IDE7IGkgPD0gdDsgaSsrKSB7CiAgICAgICAgaW50IG47CiAgICAgICAgY2luID4+IG47CiAgICAgICAgcHJpbWVGYWN0b3JpemF0aW9uKGksIG4pOwogICAgfQogICAgCiAgICByZXR1cm4gMDsKfQo=