#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
///Nume:Dima Matei
///Scoala:C.N.I "Grigore Moisil"
///Clasa: 10
///Email: [email protected]
int div(int x)
{
    int nr,nr2=0;

    for(nr=0; x%2==0; nr++, x/=2);

    if(nr!=0)
    {
      nr2++;
   }

     for(int d=3;d*d<x;d++)
     {
         for(nr=0;x%d==0;nr++, x/=d);
         if(nr!=0)
         {
          nr2++;
         }
     }
     if(x!=1)
        nr2++;
        return nr2;
}
int main()
{

    int t;
    fin>>t;
    int n,k;
    for(int i=0;i<t;i++)
    {
      fin>>n>>k;
      bool ok=false;
      while(n>=2)
      {
          if(div(n)==k)
          {
              fout<<n<<"\n";
              ok=true;
              break;
          }
          n--;
      }
      if(ok==false)
      fout<<0<<"\n";
    }
    return 0;
}