#include <stdio.h>
#define N 1000001
int v[N],a[8][N],nr[8];
void ciur()
{
	int i,j;
	for (i=2; i<N; i++)
		if (!v[i])
			for (j=i; j<N; j+=i)
				v[j]++;
	for(i=1;i<N;++i)
		a[v[i]][++nr[v[i]]]=i;
}
int cbin(int n,int k)
{
	int st=1,dr=nr[k],m;
	while(st!=dr)
	{
		m=(st+dr)/2;
		if (n<=a[k][m])
			dr=m;
		else
			st=m+1;
	}
	if(a[k][st]>n)
		--st;
	return st;
}
/*
void scrie()
{
	int i,j;
	for (i=1; i<=8; i++)
	{
		for (j=1; j<=20; j++)
			printf("%d ",a[i][j]);
		printf("\n");
	}	
}
*/
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	int t,n,k,i;
	ciur();
	//scrie();
	scanf("%d",&t);
	for (i=1; i<=t; i++)
	{
		scanf("%d%d",&n,&k);
		printf("%d\n",a[k][cbin(n,k)]);
	}
	return 0;
}