import java.util.*;

class Main {
    public static void main (String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 2; i <= 100000; i ++) {
            boolean flag = true;
            for (int j = 2; j * j <= i; j ++) {
                if (i % j == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) list.add(i);
        }

        while (q -- > 0) {
            long n = in.nextLong();
            int k = in.nextInt();
            long ans = 1L;
            for (int i = 0; i < list.size(); i ++) {
                int p = list.get(i);
                int t = 0;
                while (n != 1 && n % p == 0) {
                    t ++;
                    n /= p;
                }
                if (t >= k) ans *= qmi((long)p, t);
                if (n == 1) break;
            }
            System.out.println(ans);
        }
    }

    public static long qmi (long a, int b) {
        long res = 1L;
        while (b != 0) {
            if (b % 2 == 1) res = res * a;
            a = a * a;
            b >>= 1;
        }
        return res;
    }


}

//1. 预处理 处理得到所有素数， 得到一个数组，

//2. 计算底数和指数；  从第一个素数开始，看是否能被整除；

//3. 处理满足条件的数，

严格按照小模拟的方式去做，有更便利的方法