#include <fstream>


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

long long N;
int T;
short K , X[1000001];


void ciur(){

    long long i,j;
    for(i=2;i<=1000;i++)
        if(!X[i])
    {
        j=2;
        while(j*i<=1000000)X[j*i]++,j++;
    }


}

void findNr(long long A,short K){

    long long k;
    short q=1;
    for(k=A;k>=2 && q;k--)
        if(X[k]==K)q=0,fout<<k<<"\n";
    if(q)fout<<0<<"\n";
}

int main()
{

    fin>>T;
    ciur();
    for(int i=1;i<=T;i++){
        fin>> N >> K;

        if(!X[N] && K==1)fout<<N<<"\n";
        else if(!X[N] && K>1)fout<<0<<"\n";
        else findNr(N,K);

    }

}