#include <stdio.h>
int n,j,l,i,t, nd[1000001];;
int ciur(int n)
{
   
    int k=0,c,i;
    for(i=1;i<=n;i++)
     nd[i]=0;
    if(n%2==0)
     k++;
    for(i=3;i<=n;i+=2)
    if(nd[i]==0)
      {
                for(c=i+i+i;c<=n;c+=i<<1)
                 nd[c]=1;
                if(n%i==0)
                {
                    k++;
                    if(k>j)
                     break;
                }
      }
 
     return k;
}
int main()
{
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
                     scanf("%d %d",&n,&j);
                     int g=0;
                     for(l=n;l>=1;l--)
                      if(ciur(l)==j)
                       {
                                    printf("%d\n",l);
                                    g=1;
                                    break;
                       }
                      if(g==0)
                       printf("0\n");
    }
    return 0;
}