#include <algorithm>
#include <bitset>
#include <fstream>
#include <vector>
using namespace std;
const int kSqrt = 1e3 + 5;
const int kMax = 1e6 + 5;
const int kDiv = 8;
int n, k;
vector<int> noDiv(kMax, 0);
vector<int> v[kDiv];

void sieve()
{
	bitset<kMax> isPrime;
	isPrime.set();

	isPrime[0] = isPrime[1] = false;
	noDiv[2] = 1;
	for (int i = 4; i <= kMax; i += 2)
	{
		isPrime[i] = false;
		noDiv[i] = 1;	
	}
	
	for (int i = 3; i <= kSqrt; i += 2)
	{
		if (isPrime[i])
		{
			++noDiv[i];
			for (int j = i + i; j < kMax; j += i)
			{
				isPrime[j] = false;
				++noDiv[j];
			}
		}
	}
	for (int i = kSqrt + 1; i < kMax; i += 2)
		if (isPrime[i])
			++noDiv[i];
}
void precalcNumbers()
{
	for (int i = 1; i < kDiv; ++i)
		v[i].push_back(0);
	for (int i = 1; i < kMax; ++i)
		v[noDiv[i]].push_back(i);
}

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

	sieve();
	precalcNumbers();
	int t;	fin >> t;
	while (t--)
	{
		fin >> n >> k;
		fout << *(--lower_bound(v[k].begin(), v[k].end(), n)) << '\n';	
	}

	fin.close();
	fout.close();
	return 0;
}