//78902//
#include<fstream>
using namespace std;
int p[1000002];
int m[8][1000002];
void ciur()
{
	int i,j;
	for(i=2;i<=1000000;i+=2)
		p[i]++;
	for(i=3;i<1000000;i+=2)
		if(p[i]==0)
		{
			for(j=i;j<=1000000;j+=i)
				p[j]++;
		}
	for(i=1;i<=7;i++)
		for(j=1;j<=1000000;++j)
		{
			if(p[j]==i)
				m[i][j]=j;
			else
				m[i][j]=m[i][j-1];
		}
}
int main()
{
	int t,n,k,i,j;
	ifstream f("divprim.in");
	ofstream g("divprim.out");
	ciur();
	f>>t;
	for(j=1;j<=t;j++)
	{
		f>>n>>k;
		if(k==0)
			g<<1<<'\n';
		else
		{
			g<<m[k][n]<<'\n';
		}
	}
}