#include<cstdio>
const int MAX=1<<20;
int n,k,T,ndp[MAX],sol[MAX][8];
void cciur()
{
	for(int i=2;i<=MAX-1;i++)
		if(ndp[i]==0)
		{
			for(long long j=i;j<=MAX;j+=i)
				ndp[j]++;
			ndp[i]=1;
		}
}
void copiere(int x,int y)
{
	for(int j=0;j<=7;j++)
		sol[x][j]=sol[y][j];
}
void make_mat()
{
	for(int i=1;i<=MAX;i++)
	{
		copiere(i,i-1);
		if(ndp[i]<=7)
			sol[i][ndp[i]]=i;
	}
}
void sta()
{
	cciur();
	make_mat();
}	
int main()
{
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&T);
	sta();
	for(;T;--T)
	{
		scanf("%d%d",&n,&k);
		printf("%d\n",sol[n][k]);
	}
	return 0;
}