#include<cstdio>
#include<algorithm>
using namespace std;
#define N 1000004
int a[8][N],v[N],num[N],max;
/*bool compar(const int &a,const int &b)
{
	return (a<b);
}*/
void div(int x)
{
	for(int i=1; i*x<N-2; ++i)
	{
		bool ok=false;
		while (v[i*x]%x==0)
		{
			v[i*x]/=x;
			ok=true;
		}
		if (ok)
			++num[i*x];
	}
}
void matrice()
{
	for (int i=2; i<N-2; ++i)
		v[i]=i;
	for (int i=2; i<N-2; ++i)
		if (v[i]>1)
			div(i);
	for (int i=2; i<N-2; ++i)
		if (v[i]!=1)
			++num[i];
	for (int i=2; i<N-2; ++i)
		a[num[i]][++a[num[i]][0]]=i;
	/*for (int i=1; i<=7; ++i)
		sort(a[i]+1,a[i]+a[i][0]+1,compar);*/
}
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;
}