#include<stdio.h>
#define N 1000001
#define M 400000
char c[N];
int a[8][M];
void ciur()
{
	c[1]=1;
	for (int i=2; i<N; ++i)
		{
			if (!c[i])
				{
					++c[i];
					for (int j=i+i;j<N; j+=i)
						++c[j];
				}
			a[(int)c[i]][++a[(int) c[i]][0]]=i;
			
	    }
}
int caut (int nrd, int x)
{
	int  p=1,u=a[nrd][0],m;
	while (p<u)
	{
		m=(p+u)/2;
		if (x<=a[nrd][m])
			u=m;
		else
			p=m+1;
	}
	if (a[nrd][p]>x)
		return p-1;
	else
		return p;
}
int main()
{
	freopen ("divprim.in", "r",stdin);
	freopen ("divprim.out", "w",stdout);
	ciur();
	int t,n,k,poz;
	scanf("%d",&t);
	while (t)
	{
		scanf("%d%d",&n,&k);
		poz=caut(k,n);
		if (poz==0)
			printf("0\n");
		else
			printf("%d\n",a[k][poz]);
		--t;
	}
	fclose(stdin);
	fclose(stdout);
}