#include<fstream>
#include<vector>
using namespace std;
int v[1000002];
int haha[8][1000000],k[8];
int n;
ifstream f("divprim.in");
ofstream g("divprim.out");
void ciur()
{
	int i,j;
	for(i=2;i<=500000;i++)
	{
		if(v[i]==0)
		{   
			for(j=1;j*i<=1000000;j++)
				v[j*i]++;
		}
		haha[v[i]][++k[v[i]]]=i;
	}
	for(i=500001;i<=1000000;i++)
		haha[v[i]][++k[v[i]]]=i;
}
int cautare_binara(int i,int st,int dr,int x)
{
	int mij=(st+dr)/2;
	if(st<dr)
	{
		if(haha[i][mij]<x)
			return cautare_binara(i,++mij,dr,x);
		else
			if(haha[i][mij]>x)
				return cautare_binara(i,st,--mij,x);
			else
				if(haha[i][mij]==x)
					return mij;
	}
	return st;
}
int main()
{
	int poz,i,N,K,T;
	ciur();
	haha[0][1]=1;
	f>>T;
	for(i=1;i<=T;i++)
	{
		f>>N>>K;
		poz=cautare_binara(K,1,k[K],N);
		if(haha[K][poz]<=N)
			g<<haha[K][poz]<<endl;
		else
			g<<haha[K][--poz]<<endl;
	}
	f.close();g.close();
	return 0;
}