#include<stdio.h>

const int N = 1<<20;
int c[N],n,m;

void qqa()
{
	int i,j;
	for(i=2;i<N;++i)
		if(c[i]==0)//i este prim
			for(j=i;j<=N;j+=i)
				++c[j];
	c[1]=1;
}
int cc[8][N/2],ndv[N>>1];
int caut(int x,int qq)
{
	int i , pas = N>>1;
	for(i=0;pas;pas>>=1)
	{
		if(i+pas<=ndv[qq] && cc[qq][i+pas]<=x)
			i+=pas;
	}
	return i;
}	
void qqb()
{
	int i;
	for(i=1;i<N;++i)
		cc[c[i]][++ndv[c[i]]]=i;
}
int main()
{
	int i,k;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%ld",&m);
	qqa();
	qqb();
	for(i=1;i<=m;i++)
	{
		scanf("%ld%ld",&n,&k);
		printf("%ld\n",cc[k][caut(n,k)]);
				
	}
	return 0;
}