#include<bits/stdc++.h>
using namespace std;
int snt(int x){
	if(x<=2) return 1;
	for(int i=2;i*i<=x;i++) if(x%i==0) return 0;
	return 1;
}
int main(){
	int t;
	cin>>t;
	int dem=0;
	while(t--){
		dem++;
		int n;
		cin>>n;
		cout<<"Test "<<dem<<" ";
		int a[10001]={};
		int c=0;
		int b[10001]={};
		int d=0;
		int j=2;
		while(n>=j){
			if(n%j==0&&snt(j)){
				b[j]++;
				if(b[j]==1){
					a[c]=j;
					c++;
				}
				n/=j;
			} 
			else {
				j++;
			}
		}
		for(int i=0;i<c;i++) cout<<a[i]<<" "<<"("<<b[a[i]]<<")"<<" ";
		cout<<endl;
	}
}

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKaW50IHNudChpbnQgeCl7CglpZih4PD0yKSByZXR1cm4gMTsKCWZvcihpbnQgaT0yO2kqaTw9eDtpKyspIGlmKHglaT09MCkgcmV0dXJuIDA7CglyZXR1cm4gMTsKfQppbnQgbWFpbigpewoJaW50IHQ7CgljaW4+PnQ7CglpbnQgZGVtPTA7Cgl3aGlsZSh0LS0pewoJCWRlbSsrOwoJCWludCBuOwoJCWNpbj4+bjsKCQljb3V0PDwiVGVzdCAiPDxkZW08PCIgIjsKCQlpbnQgYVsxMDAwMV09e307CgkJaW50IGM9MDsKCQlpbnQgYlsxMDAwMV09e307CgkJaW50IGQ9MDsKCQlpbnQgaj0yOwoJCXdoaWxlKG4+PWopewoJCQlpZihuJWo9PTAmJnNudChqKSl7CgkJCQliW2pdKys7CgkJCQlpZihiW2pdPT0xKXsKCQkJCQlhW2NdPWo7CgkJCQkJYysrOwoJCQkJfQoJCQkJbi89ajsKCQkJfSAKCQkJZWxzZSB7CgkJCQlqKys7CgkJCX0KCQl9CgkJZm9yKGludCBpPTA7aTxjO2krKykgY291dDw8YVtpXTw8IiAiPDwiKCI8PGJbYVtpXV08PCIpIjw8IiAiOwoJCWNvdXQ8PGVuZGw7Cgl9Cn0=