#include <fstream>

using namespace std;
int t,contor,n,k,i,j;
short v[1000005];
int main()
{
  ifstream f("divprim.in");
  ofstream g("divprim.out");
  f>>t;
  for(i=2;i<=1000000;i++)
    if(v[i]==0)
     for(j=2*i;j<=100000;j+=i) v[j]++;
  for(contor=1;contor<=t;contor++)
  {
     f>>n>>k;
     while(v[n]!=k && n>1) n--;
     if(n==1) g<<0<<"\n";
     else g<<n<<"\n";
  }
    return 0;
}