#include<stdio.h>

int Q,v[1000001],o=1,K,N,T,x;
int te[9]={0,2,6,30,210,2310,30030,510510};
int main()
{
freopen("divprim.in","r",stdin);
freopen("divprim.out","w",stdout);
    for(int i=2;i<=1000000;++i)
        if(v[i]==0)
        for(int j=i;j<=1000000;j=j+i)
            {
                ++v[j];
            }

scanf("%d",&T);
for(int i=1;i<=T;++i)
{
    scanf("%d%d",&N,&K);
    if(te[K]>N)
    printf("0\n");
    else
    for(int j=N;j!=0;--j)
    if(v[j]==K)
    {
    printf("%d\n",j);
    j=1;
    }

}


return 0;
}