#include<stdio.h>
#define N 2000000
char v[N];
void ciur(){
	int i,j;
	v[0]=v[1]=1;
	for(j=4;j<N;j+=2)
		v[j]=1;
	//--k;
	for(i=3;i*i<N;i+=2)
		if(!v[i]){
			//--k;
			//if(!k)
				//return i;
			for(j=i+i;j<N;j+=i)
				v[j]=1;
		}
	//return 0;
}
int cauta(int n,int k){
	int div[7],p=2,i=3,j=1;
	div[0]=2;
	while (p<=n){
		if (v[i]==0){
			++j;
			p/=div[j%i];
			div[j%i]=i;
			p*=div[j%i];
		}
		i+=2;
	}
	printf("%d\n",p);
	return 0;
}
int main(){
	int n,k,t,i;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	ciur();
	scanf("%d",&t);
	for (i=0;i<t;++i){
		scanf("%d%d",&n,&k);
		cauta(n,k);
	}
	return 0;
}