#include <iostream>
#include <fstream>

using namespace std;

unsigned int prim(unsigned int n)
{
    if(n<2)
      return 0;
     
    if(n&1==0)
        return 0;
      
    unsigned int i;
    for(i=2;i<=n/2;i++)
        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=1;

    for(i=2;i<=n/2;i++)
        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);
   }
   
   f.close();
   g.close();
   
   
   
   return 0;
}