#include<fstream>

#define NMAX 1000002

using namespace std;

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

int divs[NMAX];

void ciur()
{
	for(int i=2;i<=NMAX;i++)
		if(!divs[i])
		{
			for(int j=i+i;j<=NMAX;j+=i)
				divs[j]++;
			divs[i]=1;
		}
}

int main()
{
	int n,k,t,i;
	ciur();
	fin>>t;
	while(t--)
	{
		fin>>n>>k;
		for(i=n;i;i--)
			if(divs[i]==k)
				break;
		fout<<i<<'\n';
	}
	return 0;
}