试除法

import java.util.*;
import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);

        int q = Integer.parseInt(br.readLine());

        while (q -- > 0) {
            String[] str = br.readLine().split(" ");
            long num = Long.parseLong(str[0]);
            int k = Integer.parseInt(str[1]);

            long t = num;
            for (int i = 2; i <= t / i; i++) {
                if (t % i == 0) {
                    int cnt = 0;
                    while (t % i == 0) {
                        t /= i;
                        cnt++;
                    }
                    if (cnt < k) num = num / (long) Math.pow(i, cnt);
                }
            }
            if (t > 1 && k > 1) {
                num = num / t;
            }

            out.println(num);
        }
        out.flush();
    }
}