#include <stdio.h>


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=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()
{
   FILE *f,*g;
   f=fopen("divprim.in","r");
   g=fopen("divprim.out","w");
   unsigned int T,i,n,k;
   fscanf(f,"%d",&T);
   for(i=0;i<T;i++)
   {
       fscanf(f,"%d",&n);
       fscanf(f,"%d",&k);
       fprintf(g,"%d\n",find_number(n,k));
   }
   
   fclose(f);
   fclose(g);
   


    return 0;
}