import java.util.Scanner;

class Main{
    static int n;

    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        n = scan.nextInt();
        for(int i = 1;i <= n;i ++){
            int a = scan.nextInt();
            divide(a);
        }
    }

    private static void divide(int x){
        //将时间复杂度从 O(N) 优化到 O(sqrt(N)) 的方法：
        //正整数 n 最多只包含一个大于 sqrt(n) 的质因子，反证法即可证明；
        for(int i = 2;i <= x/i;i ++)
        {
            //当出现 x%i == 0 时，代表 x 已经除尽 2~i-1 之间的所有的质因子了
            //这样代表 i 不可能有 2~i-1 之间的质因数，则保证了 i 一定是一个质数，即质因子
            //可以用反证法证明：
            //如果 i 有 2~i-1 之间的质因数(假设为 m )的话，那么在之前的 j=m(令此时的 i = j) 的步骤中，
            //while循环里出现 x = i 的情况，算法会保证继续进行 x%j 操作，直至 x%j != 0 为止
            //此时，可以发现当 x%i == 0 时，若 i 有 2~i-1 之间的质因数的话，是与算法的逻辑起冲突的
            //故我们可以说， 算法保证了此时 i 不可能有 2~i-1 之间的质因数
            if(x % i == 0)
            {
                int s = 0;
                while(x % i == 0){
                    x /= i;
                    s ++;
                }
                System.out.println(i + " "+ s);
            }
        }
        if(x > 1)   System.out.println(x + " " + 1);
        System.out.println();
    }
}