#include<iostream.h>
#include<stdio.h>

  long a[1000];

  long prim(long n)
  { long i;
      for(i=2;i*i<=n;i++)
       if(n%i==0)
	 return 0;
	 return 1;
  }


   long nrdiv(long n)
   {
     long i,s=0;
      for(i=2;i*2<=n;i++)
       { if(n%i==0 && prim(i)==1)
	   s++;
       }
      return s;
   }


  int main()
{
   long x, n, k, t=0, j, i, l;

freopen("divprim.in", "r", stdin);
freopen("divprim.out", "w", stdout);

cin>>x;

for(i=1;i<=x;i++)
{ cin>>n>>k; t=0; 
    for(j=n-1;j>=0;j--)
     { if(nrdiv(j)==k)
	{ a[i]=j;
	 t=1;
	}
       if(t)
        break;
     }

}    

  for(i=1;i<=x;i++)
  { cout<<a[i]<<endl; }


return 0;
}