#include<stdio.h>
const int N=1<<20;
int a[N];
int v[10],m[10][N>>1];
void ciur()
{
	int i,j;
	for (i=2;i<N;i++)
		if(a[i]==0)
			for(j=i;j<N;j+=i)
				a[j]++;
}

void matrice()
{	
	int i;
	for(i=2;i<N;i++)
		m[a[i]][++v[a[i]]]=i;
}
int cautbin(int a,int b) //a=n, b=k
{
	int pas,i;
	pas=1<<18;
	for(i=0;pas;pas/=2)
		if (i+pas<=v[b] && m[b][i+pas]<=a) 
			i+=pas;
	if(i==0) return 0;
	return m[b][i];
}

int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	int n,k,i,t,j;
	scanf("%d",&t);
	ciur();
	matrice();
	for(i=1;i<=t;i++)
	{
		scanf("%d %d",&n,&k);
		printf("%d\n",cautbin(n,k));
	}
	/*
	for(i=2;i<N;++i)
		printf("(%d,%d) ",i,a[i]);
	printf("\n");
	for(i=1;i<=7;i++)
	{
		for(j=1;j<=v[i];j++)
			printf("%d ",m[i][j]);
		printf("\n");
	}
	for(i=1;i<=7;i++)
		printf("%d ",v[i]);
	*/
	return 0;
	
}