#include<fstream>
#include<vector>
#include<algorithm>
#define dmax 1000003
using namespace std;
ifstream in("divprim.in");
ofstream out("divprim.out");

int t, n, k;
short int x[dmax];

vector<int>y[8];
vector<int>::iterator it;

int main()
{	
	int i,j;
	
	for(i=2; 2*i<=dmax; i++)
	{	
		if(x[i]==0)
			for(j=2*i; j < dmax; j+=i)
				x[j]++;	
		
		if(x[i]==0)
			x[i]=1;
		if(x[i] <= 8)
			y[x[i]].push_back(i);
	}

	in>>t;

	for(;t;t--)
	{	
		in>>n>>k;

		it = lower_bound(y[k].begin(), y[k].end(), n);
		
		if(it == y[k].begin() )
			out<<"0\n";
		else out<<*(it-1)<<'\n';
	}
	
	in.close();
	out.close();
	return 0;
}