#include<fstream>
#include<vector>
using namespace std;
vector<int>v(1000002,0);
int haha[8][1000000],k[8];
int n;
ifstream f("divprim.in");
ofstream g("divprim.out");
void ciur()
{
	int limita,i,j;
	for(i=2;i<=1000000;i++)
	{
		if(v[i]==0)
		{   
			for(j=1;j*i<=1000000;j++)
				v[j*i]++;
		}
		haha[v[i]][++k[v[i]]]=i;
	}
}
int cautare_binara_0(int st,int dr,int x)
{
	int mij=(st+dr)/2;
	if(st<dr)
	{
		if(haha[0][mij]<x)
			return cautare_binara_0(++mij,dr,x);
		else
			if(haha[0][mij]>x)
				return cautare_binara_0(st,--mij,x);
			else
				if(haha[0][mij]==x)
					return mij;
	}
	return st;
}
int cautare_binara_1(int st,int dr,int x)
{
	int mij=(st+dr)/2;
	if(st<dr)
	{
		if(haha[1][mij]<x)
			return cautare_binara_1(++mij,dr,x);
		else
			if(haha[1][mij]>x)
				return cautare_binara_1(st,--mij,x);
			else
				if(haha[1][mij]==x)
					return mij;
	}
	return st;
}
int cautare_binara_2(int st,int dr,int x)
{
	int mij=(st+dr)/2;
	if(st<dr)
	{
		if(haha[2][mij]<x)
			return cautare_binara_2(++mij,dr,x);
		else
			if(haha[2][mij]>x)
				return cautare_binara_2(st,--mij,x);
			else
				if(haha[2][mij]==x)
					return mij;
	}
	return st;
}
int cautare_binara_3(int st,int dr,int x)
{
	int mij=(st+dr)/2;
	if(st<dr)
	{
		if(haha[3][mij]<x)
			return cautare_binara_3(++mij,dr,x);
		else
			if(haha[3][mij]>x)
				return cautare_binara_3(st,--mij,x);
			else
				if(haha[3][mij]==x)
					return mij;
	}
	return st;
}
int cautare_binara_4(int st,int dr,int x)
{
	int mij=(st+dr)/2;
	if(st<dr)
	{
		if(haha[4][mij]<x)
			return cautare_binara_4(++mij,dr,x);
		else
			if(haha[4][mij]>x)
				return cautare_binara_4(st,--mij,x);
			else
				if(haha[4][mij]==x)
					return mij;
	}
	return st;
}
int cautare_binara_5(int st,int dr,int x)
{
	int mij=(st+dr)/2;
	if(st<dr)
	{
		if(haha[5][mij]<x)
			return cautare_binara_5(++mij,dr,x);
		else
			if(haha[5][mij]>x)
				return cautare_binara_5(st,--mij,x);
			else
				if(haha[5][mij]==x)
					return mij;
	}
	return st;
}
int cautare_binara_6(int st,int dr,int x)
{
	int mij=(st+dr)/2;
	if(st<dr)
	{
		if(haha[6][mij]<x)
			return cautare_binara_6(++mij,dr,x);
		else
			if(haha[6][mij]>x)
				return cautare_binara_6(st,--mij,x);
			else
				if(haha[6][mij]==x)
					return mij;
	}
	return st;
}
int cautare_binara_7(int st,int dr,int x)
{
	int mij=(st+dr)/2;
	if(st<dr)
	{
		if(haha[7][mij]<x)
			return cautare_binara_7(++mij,dr,x);
		else
			if(haha[7][mij]>x)
				return cautare_binara_0(st,--mij,x);
			else
				if(haha[7][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;
		switch(K)
		{
		case 0:
        poz=cautare_binara_0(1,k[K],N);
		break;
		case 1:
        poz=cautare_binara_1(1,k[K],N);
		break;
		case 2:
        poz=cautare_binara_3(1,k[K],N);
		break;
		case 3:
        poz=cautare_binara_3(1,k[K],N);
		break;
		case 4:
        poz=cautare_binara_4(1,k[K],N);
		break;
		case 5:
        poz=cautare_binara_5(1,k[K],N);
		break;
		case 6:
        poz=cautare_binara_6(1,k[K],N);
		break;
		case 7:
        poz=cautare_binara_7(1,k[K],N);
		break;
		}
		if(haha[K][poz]<=N)
			g<<haha[K][poz]<<endl;
		else
			g<<haha[K][--poz]<<endl;
	}
	f.close();g.close();
	return 0;
}