#include <iostream>
#include <fstream>

using namespace std;

ifstream fin ("divprim.in");
ofstream fout ("divprim.out");

bool bruh(int x, int k){
    int pr=0,d=2;
    while(x!=1){
        if(x%d==0){
            pr++;
            if(pr>k)
                return false;
            while(x%d==0)
                x/=d;
        }
        d++;
    }

    if(pr==k)
        return true;
    else
        return false;
}

int main(){
    int t,n,k;
    fin >> t;
    for(int i=0;i<t;i++){
        fin >> n >> k;
        while(2){
            if(bruh(n,k)==true)
                break;
            else{
                n--;
                if(n==0)
                    break;
            }
        }
        fout << n << "\n";
    }
    return 0;
}