#include <fstream>

using namespace std;
 ifstream f ("divprim.in");
 ofstream g ("divprim.out");
 /**
 Nume: Rostogolea Tudor Mihnea
 Liceu: CNI "Grigore Moisil"
 Email: [email protected]
 Clasa: X B
 **/
 int p(int x)
 {
     if(x==2)
            return 1;
     if(x%2==0)
        return 0;

     for(int d=3; d*d<=x;d+=2)
     {
         if(x%d==0)
            return 0;
     }
     return 1;
 }
 int dp(int x)
 {
     int d=0;

     for(int i=2;i<=x;i++)
     {
         if(p(i)==1 && x%i==0)
         {
             d++;
         }

     }
     return d;

 }
int main()
{
    int t, n ,k;
    f>>t;
    for(int i=0; i<t; i++)
    {
        f>>n;
        f>>k;
        int x=n+1, z=0;

         while(x>0 && z!=1)
     {
        x--;
        if(dp(x)==k)
            z=1;


     }
     g<<x<<endl;
    }
    return 0;
}