#include <bits/stdc++.h>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
bitset<1000005> fr;
int n, a[90005], m, x, k;
bool divi(int b)
{
int d, nr, p, nr1;
nr = 1;
d = a[nr];
nr1 = 0;
while(b > 1)
{
p = 0;
while(b % d == 0)
{
b /= d;
p++;
}
if(p != 0) nr1++;
d = a[++nr];
if(d * d > b && b > 1) d = b;
}
return (nr1 == k);
}
int main()
{
int i, j;
fin >> n;
fr[0] = fr[1] = 1;
for(i=2; i*i<=1000000; i++)
if(fr[i] == 0)
for(j=2; j*i<=1000000; j++)
fr[j * i] = 1;
for(i=1; i<=1000000; i++)
if(fr[i] == 0) a[++m] = i;
for(i=1;i<=n;i++)
{
fin >> x >> k;
for(j=x;j>=1 && divi(j) == false;j--)
;
fout << j << "\n";
}
fin.close();
fout.close();
return 0;
}