#include<stdio.h>
#include<math.h>
#include<string.h>
#define NMAX 1000
#define LIM 1000000
int div[1000010],prime[10000];
bool c[1000010];
void ciur()
{
    int i,j,lim;
    c[0]=c[1]=1;
    lim=1000;
    for(i=4;i<=NMAX;i+=2)
        c[i]=1;
    for(i=3;i<=lim;i+=2)
        if(!c[i])
            for(j=i*i;j<=NMAX;j=j+i+i)
                c[j]=1;
    for(i=2;i<=NMAX;i++)
        if(!c[i])
            prime[++prime[0]]=i;
}

void ciur_div()
{
    int i,j;
    div[1]=0;
    for(i=1;i<=prime[0];i++)
        for(j=prime[i]*2;j<=LIM;j=j+prime[i])
            div[j]++;
}

int main()
{
    ciur();
    ciur_div();
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    int tc,n,k,i,nu,flag;
    scanf("%d",&tc);
    while(tc)
        {
            scanf("%d%d",&n,&k);
            nu=1;
            for(i=1;i<=k;i++)
                nu=nu*prime[i];
            if(nu>n)
                {
                    printf("0\n");
                    tc--;
                    continue;
                }
            flag=0;
            for(i=n;i>=1;i--)
                if(div[i]==k || (k==1 && div[i]==0))
                    {
                        printf("%d\n",i);
                        flag=1;
                        break;
                    }
            if(!flag)
            printf("0\n");
            tc--;
        }
    return 0;
}