#include <iostream>
#include <fstream>

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;
    if(prim(n))
        s++;
    if(n%2==0)
	s++;
    for(i=3;i<=n/2;i=i+2)
        if(n%i==0&&prim(i))
            s++;
            
    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()
{
   cout << "Hello World" << endl; 
   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;
}