#include<stdlib.h>
#include<stdio.h>
using namespace std;
int nrprim[1000003];
int prim(int n,int ct)
{int i,j;

    for (i=1;i<=n;i++)
    nrprim[i]=1;
    ct=0;
    for (i=2;i<=n;i++)
       if ((nrprim[i]) && (n % i == 0))
    
        {
        ct++;
        for (j=2*i;j<=n;j+=i)
        nrprim[j]=0;
        }
   return ct;
}
 
int main()
{int ct,n,k,t,j,i,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;ct=0;
    for (j=n;j>=2;j--)
    {
    ct=prim(j,ct);
    if (ct == k)
    {
           ok = 1;
           printf("%d\n",j);
           break;
    }
    }
    if (ok==0) printf("0\n");
    }
    
return 0;
}