#include <cstdio>
const int N=1000007;
const int NN=500000;
int nrd[N],n,k,t,x,a[8][NN];
void read(){
	scanf("%d%d",&n,&k);
}
void calcul(){
	int i,j;
	nrd[1]=0;
	for (i=2;i<N;++i)
		if (nrd[i]==0)
			for (j=i;j<N;j+=i)
				++nrd[j];
	for(i=2;i<N;++i)
		a[nrd[i]][ ++a[nrd[i]][0] ]=i;
}
int rezolva(){
	int p=1,u=a[k][0],m;
	while (p!=u){
		m=(p+u)/2;
		if (n<=a[k][m])
			u=m;
		else
			p=m+1;
	}
	if (a[k][p]>u)
		--p;
	if (p==0)
		return 0;
	return a[k][p];
}
void write(){
	printf("%d\n",x);
}
int main(){
	int i;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	calcul();
	for (i=1;i<=t;++i){
		read();
		x=rezolva();
		write();
	}
	return 0;
}