#include<fstream>
using namespace std;
ifstream fin("divprim.in");
ofstream fout("divprim.out");
int t,k,n,a[1000005],s[1000005][11],i,j;
int main()
{
	fin>>t;
	s[1][0]=0;
	for(i=2;i<1000005;i++)
	{
		if(!a[i])
			for(j=i;j<1000005;j+=i)
				++a[j];
		for(j=0;j<=7;j++)
			s[i][j]=s[i-1][j];
		if(a[i]<=7)
			s[i][a[i]]=i;
	}
	for(i=1;i<=t;i++)
	{
		fin>>n>>k;
		fout<<s[n][k]<<'\n';
	}
	fin.close();
	fout.close();
	return 0;
}