#include<iostream.h>
#include<stdio.h>  
   
  long long int v[1000000], p[1000000], j;
   
/*   long long prim(long long n)  
     { long long i;  
         for(i=2;i*i<=n;i++)  
         if(n%i==0)  
        return 0;  
        return 1;  
     }  
     
     
     long long nrdiv(long long n)  
     {  
       long long i,s=0;  
        for(i=2;i*2<=n;i++)  
         { if(n%i==0 && prim(i)==1)  
          s++;  
          }  
         return s;  
      }  
*/

     long long int nrdiv(long long int n)
     {
  long long int a, b, nr;
   if(n%2==0)
     nr=1;
   else
    nr=0;  
   for (a = 3; a <= n; a += 2) {  
     if (p[a] == 0  && n%a==0) {  
       nr++;  
       for (b = a + a + a; b <= n; b += a << 1) {  
         p[b] = 1;  
       }  
     }  
   }  
   return nr;  
 }
     

     int main()  
   {  
      long long int x, n, k, t=0, j, i;  
     
   freopen("divprim.in", "r", stdin);  
   freopen("divprim.out", "w", stdout);
     
   scanf("%lld", &x);  
     
   for(i=1;i<=x;i++)  
   { cin>>n>>k; t=0;   
       for(j=n-1;j>=0;j--)  
        { if(nrdiv(j)==k)  
       { v[i]=j;  
        t=1;  
       }  
          if(t)  
          break;  
        }  
     
   }      

     for(i=1;i<=x;i++)  
      printf("%lld\n", v[i]);   
   
   
 return 0;  
}