#include <iostream>
#include <fstream>
using namespace std;

 ifstream f("divprim.in");
 ofstream g("divprim.out");
long v[1000002];
int main()  {
    int i, j, n, t, k;
f>>t;
for (i=2;i<=500000;i++)
if (v[i]==0)      {
v[i]=1;
for (j=2*i;j<=1000000;j=j+i)
v[j]++;
}
for (i=500000;i<=1000000;i++)
if (v[i]==0)
v[i]=1;
for (i=1;i<=t;i++)  {
f>>n>>k;
while (v[n]!=k && n!=0)
n--;
g<<n<<endl;
}

    f.close();
    g.close();
    return 0;
}