#include <fstream>
#include <iostream>

using namespace std;

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

bool c[1000001];

int const cst = 1000000;

short ap[1000001];

void ciur()
{
	int i = 3;

	for (i = 2; i <= cst; i += 2)
		ap[i] = 1;

	for (i = 3; i <= cst; i += 2)
	{

		if (c[i] == 0)
		{
			ap[i] = 1;
			for ( int j = 2 * i; j <= cst; j += i)
			{
				c[j] = true;
				ap[j]++;
			}
		}
		
	}
}
int main()
{
	int t, n, k, j;
	
	fin >> t;
	ciur();

	for (int i = 0; i < t; i++)
	{
		fin >> n >> k;
		if (ap[n] == k)
			fout << n <<'\n';
		else
		{
			j = n - 1;
			if (k == 7)
				j = 930930;
			while (k != ap[j] && j>0)
			{
				
				if ((k == 1 && c[j] == 0))
					break;        	
				  j--;
			}
			fout << j << '\n';
		}
	}
	return 0;
}