#include <fstream>
#define MAX 1000010

using namespace std;

int m[MAX][8];
int vec[MAX];

void CreateA()
{
	vec[1] = 0;
	for (int i = 2;i < MAX;i++)
		if(vec[i] == 0)
		for (int j = i;j < MAX;j += i)
			vec[j]++;
	/*for (int i = 1;i < 100;i++)
		cout << vec[i] << " ";*/
}

void CreateMatrix()
{
	for (int i = 1; i <= 1000000; i++)
	{
		for (int j = 0; j <= 7; j++)
		{
			if (vec[i] == j) 
				m[i][j] = i;
			else 
				m[i][j] = m[i - 1][j];
		}
	}
	//for (int i = 1;i <= 100;cout << "\n", i++)
	//	for (int j = 0;j <= 7;j++)
	//		cout << m[i][j] << " ";

}

void ReadAndSolve()
{
	ifstream f("divprim.in");
	ofstream g("divprim.out");
	int t;
	f >> t;
	for (int i = 1;i <= t;i++)
	{
		int n, k;
		f >> n >> k;
		g << m[n][k] << "\n";
	}
	f.close();
	g.close();
}

int main()
{
	CreateA();
	CreateMatrix();
	ReadAndSolve();
	return 0;
}