#include <iostream>
using namespace std;
void divide(int n)
{
    for(int i = 2;i <= n / i;i++)//n中至多只包含一个<= sqrt(n)的质因子
    //因此我们只需要遍历前面的就行
    {
        if(n % i == 0)
        {
            int s = 0;
            while(n % i == 0)
            {
                n /= i;
                s++;
            }
            cout << i  << ' ' << s << endl;
        }
    }
    if(n > 1) cout << n  << ' ' << "1" << endl;//如果遍历完之后n>1,就把那个>sqrt(n)的质因子输出
}
int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        int a;
        cin >> a;
        divide(a);
        puts("");
    }
    return 0;
}