#include<fstream>
#define dim 1000007
using namespace std;
ifstream f("divprim.in");
ofstream g("divprim.out");
int n,k,i,t,j;
long b[dim][8],a[dim];
int main()
{
	b[1][0]=0;
	for(i=2;i<dim;i++)
	{
		if(!a[i])
			for(j=i;j<dim;j+=i)
				++a[j];
		for(j=0;j<=7;j++)
			b[i][j]=b[i-1][j];
		if(a[i]<=7)
			b[i][a[i]]=i;
	}
	f>>t;
	for(i=1;i<=t;i++)
	{
		f>>n>>k;
		g<<b[n][k]<<"/n";
	}
	return 0;
}