#include <fstream>
#define MAX 1000010

using namespace std;

int m[MAX][8];
int vec[MAX];
bool v[MAX];
int ciur[79000];

void CreateCiur()
{
	v[0] = v[1] = true;
	for (int i = 3;i*i <= MAX - 2;i += 2)
	{
		v[i + 1] = true;
		if (v[i] == false)
		{
			for (int j = i*i;j < MAX;j += i)
				v[j] = true;
		}
	}
	int k = 0;
	for (int i = 1;i < MAX;i++)
		if (v[i] == false)
			ciur[++k] = i;
	ciur[0] = k;
	/*for (int i = 1;i <= 100;i++)
		cout << ciur[i] << " ";*/
}

void CreateA()
{
	for (int i = 1;i <= ciur[0];i++)
		for (int j = ciur[i];j < MAX;j += ciur[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()
{
	CreateCiur();
	CreateA();
	CreateMatrix();
	ReadAndSolve();
	return 0;
}