#include <cstdio>
#include <cmath>

int ciur[1000003];

void ciurr(){
    int n,lim;
    n=1000000;
    ciur[0]=ciur[1]=0;

    for(int i=2;i<=n;i++){
        if(!ciur[i]){
            for(int j=i*2;j<=n;j+=i){
                ciur[j]++;
            }
            ciur[i]=1;
        }
    }

}

int main(){
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);

    ciurr();
    int t,p,nr;
    scanf("%d",&t);

    for(;t;--t){
        scanf("%d%d",&p,&nr);
        for(int i=p;i>=1;--i){
            if(ciur[i]==nr){
                printf("%d\n",i);
                break;
            }
            if(i==1){
                printf("0\n");
                break;
            }
        }
    }

    return 0;
}