#include <fstream>

using namespace std;
 

unsigned int nr_div_prim(unsigned int n)
{
    unsigned int s=0,d=2;
    
    while(n!=1)
    {
        if(n%d==0)
            s++;
        while(n%d==0)
            n=n/d;
        d++;
    }
    return s;
 
}
  
unsigned int find_number(unsigned int n, unsigned int k)
{
    while(n)
    {
        if(nr_div_prim(n)==k)
            return n;
        n--;
    }
    return 0;
}
  
int main()
{
   ifstream f("divprim.in");
   ofstream g("divprim.out");
   unsigned int T,i,N,K;
   f>>T;
  for(i=0;i<T;i++)
  {
      f>>N;
      f>>K;
      g<<find_number(N,K)<<"\n";

    }
 
     
   f.close();
   g.close();
     
    
   return 0;
}