//78902//
#include<fstream>
using namespace std;
bool v[1000],ad;
int p[500];
int m[8][400000];
int main()
{
	int k[10],n,t,nrtermeni,i,j,d,nr;
	nr=1;
	for(i=2;i<998;i++)
		if(v[i]==false)
		{
			p[nr]=i;
			for(j=i+i;j<998;j+=i)
				v[j]=true;
			nr++;
		}
	
	k[1]=k[2]=k[3]=k[4]=k[5]=k[6]=k[7]=1;
	for(i=2;i<=1000000;++i)
	{
		d=i;
		j=1;
		int termeni=0;
		while(d>1)
		{
			if(d%p[j]==0)
			{
				termeni++;
				while(d%p[j]==0)
					d=d/p[j];
			}
			j++;
			if(j>=nr&&d>1)
			{
				d=1;
				termeni++;
			}
		}
		m[termeni][k[termeni]]=i;
		k[termeni]++;
	}
	
	ifstream f("divprim.in");
	ofstream g("divprim.out");
	f>>t;
	for(j=1;j<=t;j++)
	{
		f>>n>>nrtermeni;
		if(nrtermeni==0)
			g<<1<<'\n';
		else
		{
			for(i=1;i<=n;i++)
				if(m[nrtermeni][i]>n)
				{
					g<<m[nrtermeni][i-1]<<'\n';
					break;
				}
		}
	}
}