#include <stdio.h>
long int n,T,k,i,j,l,nr,x;
long int c[1000000];
int main()
{
    freopen("divprim.in","rt",stdin);
    scanf("%ld", &T);
    freopen("divprim.out","wt",stdout);
    while(T--)
          {
             scanf("%ld %ld", &n,&k);
             x=n;
             while(x)
                   {
                     nr=0;
                     for (i=2;i<=x;++i)
                           c[i]=1;
                     for (i=2;i<=x;++i)
                           if (c[i]==1)
                               {
                                     nr++;
                                    for (j=i+i;j<=x;j+=i)
                                          c[j]=0;
                               }
                      if (nr==k)
                           {
                                printf("%ld\n", &x);
                                break;
                            }
                            else if (x==1)
                                       printf("0\n");
                            x--;
                    }
            }
return 0;
}