#include <cstdio>
using namespace std;

bool a[100003];
int b,k,j,i,n,nr,ok,t;
int main ()
{
    freopen("divprim.in", "r", stdin);
    freopen("divprim.out", "w", stdout);
    a[1]=a[0]=1;
    for(i=3;i<=100000;i=i+2)
    {
        if(a[i]==0)
        {
            for(j=i*3;j<=100000;j=j+i*2)
                a[j]=1;
        }
    }
    scanf("%d", &n);
    for(i=1;i<=n;++i)
    {
        scanf("%d%d", &b, &k);
        ok=1;
        for(j=b;j>1&&ok;--j)
        {
            nr=0;
            if((a[j]==0&&j%2!=0)||j==2)
            {
                if(k==1) printf("%d\n", j),ok=0;
            }
            else
            {
                if(j%2==0) ++nr;
                for(t=3;t<=j&&nr<=k;t=t+2)
                {
                    if(a[t]==0&&j%t==0) ++nr;
                }
                if(nr==k)  printf("%d\n", j),ok=0;
            }
        }
        if(ok) printf("0\n");
    }
    return 0;
}