#include <stdio.h>
#include <string.h>

int i,j,T,n,k,prim[1000000],prime[1000000];

void ciur(int prim[],int x)
{
  int nrprim,l;  
  memset(prime,0,sizeof(prime));  
  for (l=2;l<=x;++l)
  {  
      nrprim=0;  
    for (i = 2; i <= l; ++i)
        prime[i] = 1;
    for (i = 2; i <=l; ++i)
        if (prime[i] && l%i==0)
        {
            nrprim++;
            for (j = i+i; j <= n; j += i)
                prime[j] = 0;
        }
        prim[l]=nrprim;
    }
}

int main()
{
    int ok;
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    scanf("%d\n", &T);
    while (T--)
    {
        scanf("%d %d\n", &n,&k);
        memset(prim,0,sizeof(prim));
        ciur(prim,n);
        ok=1;
        for (i=n;i>=1;--i)
             if (prim[i]==k)
                  {
                        printf("%d\n", i);
                        ok=0;
                        break;
                    }
               if (ok) printf("0\n");
          //for (i=1;i<=n;++i)
          //printf("%d ", prim[i]);
          //printf("\n");     
    }
    return 0;
}