#include<fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int n,T,k,i,j,t,ok;
int v[1000010];
int main(){
    for(i=2;i<=1000000;i++){
        if(v[i]==0){
            v[i]=-1;
            for(j=i+i;j<=1000000;j+=i){
                v[j]++;
            }
        }
    }
    fin>>T;
    for(t=1;t<=T;t++){
        fin>>n>>k;
        ok=0;
        for(;n>=1;n--)
            if(v[n]==k){
                fout<<n<<"\n";
                ok=1;
                break;
            }
        if(ok==0){
            fout<<0<<"\n";
        }
    }

    return 0;
}