#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);
	}

	y[0].push_back(1);
	
	in>>t;

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

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