#include<fstream.h>
ifstream f("divprim.in");
ofstream g("divprim.out");
int t,k,n,a[1000005],s[1000005][11],i,j;
int main()
{
	f>>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++)
	{
		f>>n>>k;
		g<<s[n][k]<<'\n';
	}
	f.close();
	g.close();
	return 0;
}