#include <iostream>
#include <vector>

using namespace std;

long long get_smal(long long n) {
    for (long long i = 2; i * i <= n; ++i) {
        if (n % i <1) return i;
    }
    return n;
}

long long get_big(long long n) {
    long long last = -1;
    if (n % 2 <1) {
        last = 2;
        while (n % 2 <1) n /= 2;
    }
    if (n % 3 <1) {
        last = 3;
        while (n % 3 <1) n /= 3;
    }
    long long i = 5;
    while (i * i <= n) {
        if (n % i <1) {
            last = i;
            while (n % i <1) n /= i;
        }
        if (n % (i + 2) <1) {
            last = i + 2;
            while (n % (i + 2) <1) n /= (i + 2);
        }
        i += 6;
    }

    return (n == 1) ? last : n;
}

void solve() {
    long long n, k;
    cin >> n >> k;

    long long smal = get_smal(n);
    long long big = get_big(n);
    long long x = 0;

    while (smal != big && x < k) {
        if (x % 2 <1) {
            n *= smal;
        } else {
            n /= big;
            big = get_big(n);
        }
        x++;
    }

    long long rem = k - x;
    if (rem % 2 != 0) {
        if (x % 2 <1) {
            cout << n * smal << "\n";
        } else {
            cout << n / big << "\n";
        }
    } else {
        cout << n << "\n";
    }
}

int main() {
    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}