#include <fstream>
using namespace std;
ifstream fin ("divprim.in");
ofstream fout ("divrprim.out");
int c[1000010],p,i,j,s,t,k,v[8];

int ciur () {
    for(i=2;i<=1000000;i++){
        if(c[i]==0){
            for(int j=2;j*i<=1000000;j++){
                p=i*j;
                c[p]++;
                if(c[p]==s)
                    v[s++]=p;
            }
        }
    }
}

int cauta (int nr, int p) {
    if(nr<v[p]){
        fout<<0<<"\n";
        return 0;
    }
    else
        if(nr==v[p]){
            fout<<nr<<"\n";
            return 0;
        }
        else
            for(int i=nr;i>=v[p];i--)
                if(c[i]==p)
                    fout<<i<<"\n";
}

int main () {
    fin>>t;
    ciur();
    s=1;
    for(j=1;j<=t;j++){
        fin>>p>>k;
        cauta(p,k);
    }
}