#include <cstdio>
const int N=1000007;
int nrd[N],n,k,t,x;
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];
}
int rezolva(){
	int i;
	for (i=n;i>=1;--i)
		if (nrd[i]==k)
			return i;
	return 0;
}
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;
}