#include<fstream>;
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");

int divizori_primi(int n){
    int i,k,c=0;
    i=2;
    while (n>1){
        if (n%i==0){
            k=0;
            c++;
            while (n%i==0){
            k=k+1;
            n=n/i;
        }

    }
    i=i+1;
    }
    return c;

}
int x,a,b,i,c;
int main() {

    fin>>x;
    for(i=1;i<=x;i++){
        fin>>a>>b;
        while(a!=0){
            if(divizori_primi(a)==b){
                c=a;
                break;
            }
            a--;
        }
        fout<<c;
        fout<<endl;

    }


}