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

using namespace std;

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

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

void generare ()
{
 int i, j;
    v[1] = 1;
    for (i=2; i<=1000000; i++)
    {
        if (v[i] == 0)
        {
            for (j=2*i; j<=1000000; j=j+i)
                 v[j] ++;
        }
    }
}

int getnumar (int nr, int div)
{
    int i;
     for (i=nr; i>=1; i--)
     {
         if (v[i] == div)
             return i;
     }
   return 0;
}

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