#include <stdio.h>
#define N 1000005
#define M 400000
char c[N];
int a[7][M];
void ciur()
{
	c[1]=1;
	for (int i=2; i<N; i++)
		if (!c[i])
			for (int 	j=i; j<N; j+=i)
				c[j]++;
}
void matrice()
{
	for (int i=1; i<N; i++)
		a[c[i]][++a[c[i]][0]]=i;
}
int n,k;
void binarz()
{
	int p,u,m;
	p=1;
	u=a[k][0];
	while (p<u)
	{
		m=(p+u)/2;
		if (n<a[k][m])
			u=m;
		else
			p=m+1;
	}
	if(a[k][p]>n)
		--p;
	if(p)
		printf("%d\n",a[k][p]);
	else
		printf("0\n");
}

int main()
{
	int t,i;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d\n",&t);
	
	ciur(); 
	matrice();
	
	for (i=1; i<=t; i++)
	{
		scanf("%d%d",&n,&k);
		binarz();
	}
}