#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

void find_factor(vector<int>& factor, long long n) {
    while (n % 2 == 0) {
        factor.push_back(2);
        n /= 2;
    }
    for (long long i = 3; i * i <= n; i += 2) {
        while (n % i == 0) {
             factor.push_back(i);
            n /= i;
        }
    }
    if (n > 2) {
        factor.push_back(n);
    }
    factor.push_back(-1);  // 结束符
}

long long delete_factor(const vector<int>& factor, int k) {
    long long res = 1;
    int i = 0, j = 1;

    while(factor[i] != -1){
        j = i + 1;
        while(factor[i] == factor[j]) j++;
        int len = j - i;
        if(len >= k) res *= pow(factor[i], len);

        i = j;
    }

    return res;
}

int main() {
    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        long long n;
        int k;
        cin >> n >> k;
        vector<int> factor;
        find_factor(factor, n);
        cout << delete_factor(factor, k) << endl;
    }

    return 0;
}