#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;
if (k>8)
g<<0<<endl;
else {
while (v[n]!=k && n!=0)
if (k>=8 && n<9699690)
n=0;
else if (k>=7 && n<510510)
n=0;
else if (k>=6 && n<30030)
n=0;
else if (k>=5 && n<2310)
n=0;
else if (k>=4 && n<210)
n=0;
else
n--;
g<<n<<endl;
}
}
    f.close();
    g.close();
    return 0;
}