#include<cstdio>
#include<algorithm>
using namespace std;
#define N 1000004
int a[8][N],num[N],max;
bool v[N];
void div()
{
	int d=2;
	while (d*d<N-2)
	{
		if (!num[d])
		{
			++num[d];
			for (int i=d+d; i*i<N-2; i+=d)
				++num[i];
		}
		++d;
	}
}
void matrice()
{
	div();
	for (int i=2; i<N-2; ++i)
		a[num[i]][++a[num[i]][0]]=i;
}
int caut(int x, int t)
{
	int p=1,u=a[t][0],m;
	while (p!=u)
	{
		m=(p+u)/2;
		if (a[t][m]>=x)
			u=m;
		else
			p=m+1;
	}
	if (a[t][p]>x)
		return p-1;
	return p;
}
void citire()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	short int t;
	scanf("%hd",&t);
	while (t)
	{
		int n,k;
		scanf("%d%d",&n,&k);
		if (n<2)
			printf("0\n");
		else
			if (k==0) printf("1\n");
		else
		{
		int g=caut(n,k);
		if (g)
			printf("%d\n",a[k][g]);
		else printf("0\n");
		}
		--t;
	}
}
int main()
{
	matrice();
	citire();
	return 0;
}