#include <fstream>
#include <vector>

using namespace std;

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

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

void factorizare()
{
	G[0].push_back(1);
	for(int i=2;i<=NMAX;++i)
	{
		int x = i , d = 2 , nr = 0;
		if(x%d==0) {
			nr++;
			while(x%d==0) x/=d; 
		}
		for(d=3;d*d<=x && nr<=7;d+=2)
			if(x%d==0) {
			nr++;
			while(x%d==0) x/=d; 
			}

		if(x>1) nr++;
		if(nr<=7) G[nr].push_back(i);
	}
}

void binsearch(int l,int r)
{
	if(l>r) return;
	int	m = l + (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()
{
	factorizare();
	for(fin>>T;T;T--)
	{
		fin>>nr>>k;
		binsearch(0,G[k].size()-1);
		fout<<ans<<'\n'; 
		ans = 0;
	}
	return 0;
}