#include <stdio.h>
int n,j,l,i,t;
char nd[1000001*8];
int ciur(int n)
{
   
    int k=0,c,i ;
    for(i=3;i<=n;i+=2)
     nd[i]=0;
    if(n%2==0)
     k++;
    for (i = 3; i <= n; i += 2) 
      if (nd[i] == 0) 
      {
        for (c =i*i ; c <= n; c += i*i ) 
          nd[c] = 1;
      if(n%i==0)
         k++;     
        }
     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;
}