#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

unsigned int prim(unsigned int n)
{
    if(n<2)
      return 0;
     
    if(n==2)
        return 1;
         
    if(n%2==0)
       return 0;
         
    unsigned int i;
    for(i=3;i<=n/2;i=i+2)
        if(n%i==0)
            return 0;
    
    return 1;
         
}
 
unsigned int nr_div_prim(unsigned int n)
{
    unsigned int i,s=0,d=2;
    if(prim(n))
        return 1;
    
    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;
}