#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 1000001;
vector<int> G[8];
int T , nr , k , ans , dprimi[NMAX];

void ciur()
{
	for(int i=2;i<NMAX;++i)
		if(dprimi[i]==0)
		for(int j=i+i;j<NMAX;j+=i)
			dprimi[j]++;

	G[0].push_back(1);
	for(int i=2;i<NMAX;++i)
		if(dprimi[i]<=7)
			G[dprimi[i]].push_back(i);
}

void binsearch(int l,int r)
{
	if(l>r) return;
	int	m = (r + l)/2;
	if(G[k][m]>nr)
		binsearch(l,m-1);
	else
	{
		ans = max(ans,G[k][m]);
		binsearch(m+1,r);
	}
}

int main()
{
	ciur();
	for(fin>>T;T;T--)
	{
		fin>>nr>>k;
		binsearch(0,G[k].size());
		fout<<ans<<'\n'; 
		ans = 0;
	}
	return 0;
}