#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define nl "\n"
bool isPrime(int n) { 
    if (n <= 1) return false; 
    if (n <= 3) return true; 
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2){ 
        if (n % i == 0) return false; } 
    return true; 
}

ll small(ll n) {
    for (ll i = 2; i <= n; i++) {
        if(isPrime(i) && n % i == 0) return i;
    }
}

ll large(ll n) {
    for (ll i = n; i >= 2; i--) {
        if(isPrime(i) && n % i == 0) return i;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;
    cin>>t;
    while(t--){
        ll x, k; cin>>x>>k;
        char ch = 'r';
        while (k--) {
            if (ch == 'r') {
                int p = small(x);
                x *= p;
                ch = 'h';
            }
            else {
                int p = large(x);
                x /= p;
                ch = 'r';
            }

        }

        cout<<x<<nl;
    }

    return 0;
}