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

int T, N, K;
int   t;
int ff[4000000];


int main(){

    for (int i=2;i<=4000000;i++){
        if(ff[i]==0){
            for(int j=2*i; j<=400000;j+=i)
                ff[j]++;
            }
    }
    fin>>T;
    for (int i=0; i<T; i++){
        fin>>N>>K;
        int nr=0;
        for(int t=N;t>1;t--){
            //cout<<t<<" "<<ff[t]<<endl;
            if(ff[t]==K){
                fout<<t<<endl;
                break;
            }
            nr++;
            }
        if(nr==N-1)
            fout<<0<<endl;
    }



    return 0;
}