#include <fstream>

using namespace std;

#define MAX 1000000

int v[MAX]={0},prim[MAX];

void nr_prime()
{
    unsigned int i,j;
    for(i=2;i<=MAX;i++)
        prim[i]=1;
        
     for(i=2;i<=MAX;i++)
        if(prim[i])
            for(j=i+i;j<=MAX;j=j+i)
                prim[j]=0;
                
}

unsigned int nr_div_prim(unsigned int n)
{
    unsigned int i,s=0;
    if(prim[n])
        return 1;
    for(i=2;i<=n/2;i++)
    {  
        while(prim[i]==0&&i<=n/2)
            i++;
        if(n%i==0)
            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()
{
   
   ifstream f("divprim.in");
   ofstream g("divprim.out");
   unsigned int T,i,n,k;
   nr_prime();
   f>>T;
   for(i=0;i<T;i++)
   {
      f>>n;
      f>>k;
      g<<find_number(n,k)<<"\n";
      
   }

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