#include <bits/stdc++.h>
using namespace std;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

const int N = 1000005;
int dprim[N];
int q, n, k;

vector<int> v[10];

int Bs(int n, int k)
{
	int st = 0, dr = v[k].size() - 1, mij = 0, sol = -1;
	while (st <= dr)
	{
		mij = (st + dr) / 2;
		if (v[k][mij] <= n)
			sol = mij, st = mij + 1;
		else dr = mij - 1;
	}
	return (sol == -1 ? 0 : v[k][sol]);
}

int main()
{
	ios_base::sync_with_stdio(false);
	fin.tie(0);
	fout.tie(0);

	for (int i = 2; i < N; ++i)
		if (!dprim[i])
			for (int j = 1; i * j < N; ++j)
				++dprim[i * j];

	for (int i = 2; i < N; ++i)
		v[dprim[i]].push_back(i);

	fin >> q;
	while (q--)
	{
		fin >> n >> k;
		fout << Bs(n, k) << '\n';
	}
}