#include <fstream>
#include <iostream>
#define MAXN 1000001
using namespace std;

int n_div[MAXN], sol[MAXN][8];

void ciur()
{
	for(int i = 2; i <= MAXN; ++i)
	{	
		if(!n_div[i])
			for(int j = i; j <= MAXN; j += i)
				++n_div[j];
	
		for(int j = 0; j <= 7; ++j)
			sol[i][j] = sol[i - 1][j];
		
		if(n_div[i] <= 7)
			sol[i][n_div[i]] = i;
	}
	
}

int main()
{
	ifstream f("divprim.in");
	ofstream g("divprim.out");
	
	int t, n, k;
	
	f >> t;
	
	ciur();
	
	for(int i = 1; i <= t; ++i)
	{
		f >> n >> k;
		
		if(k == 0 && n == 1)
			g << 1 << '\n';
		else 
			g << sol[n][k] << '\n';
	}
	
	f.close();
	g.close();
	
	return 0;
}