#include <fstream>
#include <bitset>

using namespace std;
ifstream cin("divprim.in");
ofstream cout("divprim.out");
const int DIM = 1000001, MAXP = 78501, MAXK = 8;

int turbociur[DIM];
int divi[DIM][MAXK];
void buildciur();
void buildmat();
int main()
{
	buildciur();
	buildmat();

	int t, n, k;
	cin >> t;
	while (t)
	{
		cin >> n >> k;
		cout << divi[n][k] << '\n';

		--t;
	}
	getchar();
	getchar();
	return 0;
}

void buildmat()
{
	for (int i = 1; i <= DIM - 1; ++i)
	{
		for (int j = 1; j <= MAXK - 1; ++j)
		{
			divi[i][j] = divi[i - 1][j];
		}
		divi[i][turbociur[i]] = i;
	}
}

void buildciur()
{
	int last = 1;
	for (int i = 2; i * i <= DIM - 1; ++i)
	{
		if (!turbociur[i])
		{
			for (int j = 1; j * i <= DIM - 1; ++j)
			{
				turbociur[i * j]++;
			}	
		}
	}
}