#include <fstream>

#include <cstring>

#include <vector>



#define MAX_N 1000005

#define MAX_K 10

using namespace std;


ifstream f("divprim.in");
ofstream g("divprim.out");
int T, N, K, D[MAX_N];
bool prim[MAX_N];

vector<int> P[MAX_K];
void ciur()
{
memset (prim, true, sizeof(prim));
for (int i = 2; i <= MAX_N; i++)
if (prim[i]) {
D[i] = 1;
for (int j = 2 * i; j <= MAX_N; j += i) {
prim[j] = false;
D[j]++;
}
}
}

void precompute()
{
for (int i = 1; i <= MAX_N; i++)
P[D[i]].push_back(i);
}

int bsearch()
{
int lo = 1, hi = P[K].size(), mid;

while (lo <= hi) {
mid = (lo + hi) / 2;
if (P[K][mid - 1] <= N)
lo = mid + 1;
else
hi = mid - 1;
}

if (P[K][mid - 1] > N)
mid--;
if (P[K][mid - 1] <= N && mid > 0)
return P[K][mid - 1];
else
return 0;
}

int main()
{
ciur();
precompute();

f >> T;
while (T--) {
f >> N >> K;
g << bsearch() << '\n';
}

f.close();
g.close();

return 0;
}