#include<fstream>
#include<vector>
#define NMAX 1000005
#define pb push_back 
using namespace std; 

ifstream in("divprim.in"); 
ofstream out("divprim.out"); 
int T, nr, rez, dprimi[NMAX],K;
vector< int > G[8];
void ciur() 
{
	int i,j;
	for(i = 2; i < NMAX; i++) 
		if(!dprimi[i])
			for(j = i; j <= NMAX; j+=i) 
				dprimi[j]++; 
			
			G[0].pb(1); 
			for(i = 2; i <= NMAX; i++) 
				if(dprimi[i] <= 7 )
					G[dprimi[i]].pb(i); 
}
void binary_search(int left, int right) 
{
	if(left > right) return; 
	int mij = left + (right - left)/2; 
	if(G[K][mij] > nr) 
		binary_search(left, mij - 1); 
	else 
	{
		rez = max(rez, G[K][mij]); 
		binary_search(mij+1, right); 
	}
}
int main() 
{
	int i;
	ciur(); 
	in >> T; 
	for(i = T; i >= 1; i--) 
	{
		in >> nr >> K; 
		binary_search(0, G[K].size() - 1);
		out << rez << '\n'; 
		rez = 0; 
	}
}