#include<stdio.h>

int Q,v[1000001],o=1,K,N,T,x,vn[100001],vk[100001];
int te[9]={0,2,6,30,210,2310,30030,510510},max;
int main()
{

freopen("divprim.in","r",stdin);
freopen("divprim.out","w",stdout);
scanf("%d",&T);
for(int i=1;i<=T;++i)
{
    scanf("%d %d",&vn[i],&vk[i]);
    if(vn[i]>max)
    max=vn[i];
}
    for(int i=2;i<=max;++i)
        if(v[i]==0)
        for(int j=i;j<=max;j=j+i)
            {
                ++v[j];
            }
for(int i=1;i<=T;++i)
{
    if(te[vk[i]]>vn[i])
    printf("0\n");
    else
    for(int j=vn[i];j!=0;--j)
    if(v[j]==vk[i])
    {
    printf("%d\n",j);
    j=1;
    }

}


return 0;
}