#include <fstream>
#include <string.h>

using namespace std;

ifstream f ("divprim.in");
ofstream g ("divprim.out");

int t, n, k, i, v[1000002];

int divprim (int numar, int divizori)
{
    memset(v, 0, sizeof(v));
    int i, j;
     for (i=2; i<=numar; i++)
     {
         if (v[i] == 0)
         {
           for (j=i+i; j<=numar; j=j+i)
              v[j] ++;
         }
     }
     for (i=numar; i>= 1; i--)
     {
         if (v[i] == divizori)
            return i;
     }
   return 0;
}

int main()
{
   f >> t;
     for (i=1; i<=t; i++)
     {
         f >> n >> k;
        g << divprim(n, k) << '\n';
     }
    return 0;
}