#include<stdio.h>
int c[1000011];
void ciur()
{
    int i,j;
    for(i=2;i<=1000000;i=i+2)
        ++c[i];
    for(i=3;i<=1000000;i=i+2)
        if(c[i]==0)
            for(j=i;j<=1000000;j=j+i)
                ++c[j];
}
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    int n,k,t,i;
    scanf("%d",&t);
    ciur();
    while(t)
    {
        t--;
        scanf("%d%d",&n,&k);
        i=n;
        while(c[i]!=k&&i>=1)
            i--;
        if(i==1)
            printf("0\n");
        else
            printf("%d\n",i);
    }
    return 0;
}