#include<stdlib.h>
#include<stdio.h>

int i,ct;
int prim(int n)
{int i;
    for (i=2;i<=n/2;i++)
    if (n % i == 0) return 0;
    return 1;
}
int div(int n)
{
    int i;
        for (i=2;i<=n/2;i++)
    if ((n % i == 0) && (prim(i)==1)) ct++;
    
} 

int main()
{int n,k,t,j, ok;
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    
    scanf("%d",&t);
    
    for (i=1;i<=t;i++)
    {
        scanf("%d %d",&n,&k);
    
    ok = 0;
    for (j=n;j>=2;j--)
    {
    ct = 0;
    div(j);
    if (ct == k)
    {
           ok = 1;
           printf("%d\n",j);
           break;
    }
    }
    if (ok==0) printf("0\n");
    }
return 0;
}