#include<fstream>
#include <cstring>
using namespace std;
int p[1000000];
int M[8][1000000];
int s[100000];
int K;
int cautare (int n, int o, int j)
{
	int m;
	if(n>M[K][j]||n<M[K][o]) return 0;
	else
	{
		m =(o+j)/2;

		if (n==M[K][m])
			return M[K][m];

		if (n<M[K][m]&&n>M[K][m-1])
			return M[K][m-1];

		if (n>M[K][m]&&n<M[K][m+1])
			return M[K][m];

		if (n<M[K][m])
			return cautare (n,o,m-1);
		else
			return cautare (n,m+1,j);
	}
}
int main()
{
	int a=1,b=1,c=1,d=1,e=1,f=1,g=1;
	int h,i,j=0,n,T;
	memset(p, 0x0, sizeof(p));
	memset(M, 0x0, sizeof(M));
	memset(s, 0x0, sizeof(s));
	ifstream fi("divprim.in");
	ofstream fo("divprim.out");
	n=1000000;
	for(i=2; i<=n; ++i)
	{
		if(p[i]==0)
			for(j=i;j<=n;j+=i)
				p[j]++;
	}
	for(i=2; i<=n; ++i)
	{
		if (p[i]==1) {M[1][a]=i; ++a;}
		if (p[i]==2) {M[2][b]=i; ++b;}
		if (p[i]==3) {M[3][c]=i; ++c;}
		if (p[i]==4) {M[4][d]=i; ++d;}
		if (p[i]==5) {M[5][e]=i; ++e;}
		if (p[i]==6) {M[6][f]=i; ++f;}
		if (p[i]==7) {M[7][g]=i; ++g;}
	}
	fi>>T;
	for(h=1; h<=T; ++h)
	{
		fi>>n;
		fi>>K;
		switch (K)
		{
		case 1:
			j=a-1; break;
		case 2:
			j=b-1; break;
		case 3:
			j=c-1; break;
		case 4:
			j=d-1; break;
		case 5:
			j=e-1; break;
		case 6:
			j=f-1; break;
		case 7:
			j=g-1; break;
		default:
			s[h]=1;
		}
		s[h]=cautare(n,1,j);
	}
	for(i=1; i<=h-1; ++i)
		fo<<s[i]<<"\n";
	return 0;
}