#include<stdio.h>

using namespace std;
int sw[1000001];
int main()
{
    int i,t,n,k,j;
    for(i=2;i<=100001;++i)
        if(sw[i]==0)
        {
            sw[i]=1;
            for(j=i+i;j<=100001;sw[j]++,j+=i);

        }

    freopen("divprim.in","r",stdin);
    scanf("%d",&t);
    freopen("divprim.out","w",stdout);
    for(i=1;i<=t;++i)
    {   scanf("%d %d",&n,&k);
        if(sw[n]==k) printf("%d\n",n);
        else
        {
            for(j=n-1;j>=1 && sw[j]!=k;--j);
            if(j!=1) printf("%d\n",j);
            else printf("0\n");
        }
    }
    fclose(stdin);fclose(stdout);
    return 0;
}