#include <iostream>
 
using namespace std;
 
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        int i = 2; 
        while(i <= n)
        {
            if(n%i == 0)
            {
                int d = 0;
                while(n%i == 0)
                {
                    n /= i;
                    d++;
                }
                cout << i << " (" << d << ") ";
            }
            i++;
        }  
        cout << '\n';
    }
}

I2luY2x1ZGUgPGlvc3RyZWFtPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmludCBtYWluKCkKewogICAgaW50IHQ7CiAgICBjaW4gPj4gdDsKICAgIHdoaWxlKHQtLSkKICAgIHsKICAgICAgICBpbnQgbjsKICAgICAgICBjaW4gPj4gbjsKICAgICAgICBpbnQgaSA9IDI7IAogICAgICAgIHdoaWxlKGkgPD0gbikKICAgICAgICB7CiAgICAgICAgICAgIGlmKG4laSA9PSAwKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBpbnQgZCA9IDA7CiAgICAgICAgICAgICAgICB3aGlsZShuJWkgPT0gMCkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBuIC89IGk7CiAgICAgICAgICAgICAgICAgICAgZCsrOwogICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgY291dCA8PCBpIDw8ICIgKCIgPDwgZCA8PCAiKSAiOwogICAgICAgICAgICB9CiAgICAgICAgICAgIGkrKzsKICAgICAgICB9ICAKICAgICAgICBjb3V0IDw8ICdcbic7CiAgICB9Cn0=

Mwo2MCAKMTI4CjEyNw==

3
60 
128
127