#include<stdio.h>
const int N=1000000;
int d[N],k;
int a[8][N],nr[8],i,n,t;


void precalcul()
{
	int i,j;
	for(i=2;i<N;i++)
	{
		if(d[i]==0)//daca i este prim
			for(j=i;j<N;j+=i)//pentru fiecare j, multiplu al lui i
				d[j]++;//incrementez nr de div primi
	}
}

void completare_a()
{
	int i,lin;
	for(i=2;i<N;i++)
	{
		lin = d[i];
		++nr[lin];
		a[lin][nr[lin]] = i;
		//a[d[i]][ ++ nr[d[i]] ] = i;//adaug i pe linia d[i]
	}
}

void afisare_d()
{
	int i;
	for(i=2;i<50;i++)
		printf("d[%d] = %d\t",i,d[i]);
}

void afisare_a()
{
	int i,j;
	for(i=1;i<7;i++)
	{
		for(j=1;j<=20;j++)
			printf("%d ",a[i][j]);
		printf("\n");
	}
}

int cautbin(int k,int n)
{
	int i,pas=1<<20;
	for(i=0;pas!=0;pas>>=1)
	{
		if(i+pas<=nr[k] && a[k][i+pas]<=n)
			i+=pas;
	}
	return a[k][i];
}

int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	precalcul();
	//afisare_d();
	completare_a();
	//afisare_a();
	for(i=1;i<=t;i++)
	{
		scanf("%d%d",&n,&k);
		printf("%d\n",cautbin(k,n));
	}
	return 0;
}