#include <fstream>
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int v[100010], k[100010], ciur[1000001], mx, i, j, t;
void ciur1(int n)
{
	for (int i = 2 * n; i <= mx; i += n)
		ciur[i]++;
}
int main()
{
	f >> t;
	int c[9];
	c[1] = 2;
	c[2] = 3 * c[1];
	c[3] = 5 * c[2];
	c[4] = 7 * c[3];
	c[5] = 11 * c[4];
	c[6] = 13 * c[5];
	c[7] = 17 * c[6];
	c[8] = 19 * c[7];
	for (int i = 1; i <= t; i++)
	{
		f >> v[i] >> k[i];
		if (v[i] > mx)
			mx = v[i];
	}
	ciur1(2);
	ciur[2] = 1;
	for (i = 3; i <= mx; i+=2)
		if (ciur[i] == 0)
		{
			ciur1(i);
			ciur[i] = 1;
		}
	for (i = 1; i <= t; i++)
	{
		 int ok = 0;
		while (ciur[v[i]] != k[i])
		{
			if (v[i] <= c[k[i]] - 1)
			{
				ok = 1;
				g << 0 << "\n";
				break;
			}
			else
				if (k[i] == 0 && v[i] > 1)
				{
					g << 1 << " ";
					ok = 1;
					break;
				}
			v[i]--;
		}
		if(ok==0)
		    g << v[i] << "\n";
	}
}