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

int T, N, K;
int   t;
const int DIM=4000005;
int ff[DIM];


int main(){

    for (int i=2;i<DIM;i++){
        if(ff[i]==0){
            for(int j=i; j<DIM;j+=i)
                ff[j]++;
            }
    }
    fin>>T;
    for (int i=0; i<T; i++){
        fin>>N>>K;
        if(K==0){
            fout<<1<<"\n";
            continue;
        }
        int nr=0;
        for(int t=N;t>1;t--){
            if(ff[t]==K){
                fout<<t<<"\n";
                break;
            }
            nr++;
            }
        if(nr==N-1)
            fout<<0<<"\n";
    }



    return 0;
}