#include<cstdio>
using namespace std;
#define MAX_N 1000000
char a[8][MAX_N+1], ciur[MAX_N+1];
void ciuruire() {
	int i, j;
	for(i=2;i*i<=MAX_N;){
		for(j=1;j*i<=MAX_N;j++)
			ciur[i*j]++;
		while(ciur[i]!=0)
			i++;
	}
	for(i=2;i<=MAX_N;i++){
		if(ciur[i]==1)	a[1][i]=i;
		else			a[1][i]=a[1][i-1];
		if(ciur[i]==2)	a[2][i]=i;
		else			a[2][i]=a[2][i-1];
		if(ciur[i]==3)	a[3][i]=i;
		else			a[3][i]=a[3][i-1];
		if(ciur[i]==4)	a[4][i]=i;
		else			a[4][i]=a[4][i-1];
		if(ciur[i]==5)	a[5][i]=i;
		else			a[5][i]=a[5][i-1];
		if(ciur[i]==6)	a[6][i]=i;
		else			a[6][i]=a[6][i-1];
		if(ciur[i]==7)	a[7][i]=i;
		else			a[7][i]=a[7][i-1];
	}
}
int main(){
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	int n;
	scanf("%d",&n);
	ciuruire();
	while(n--!=0){
		int x, k;
		scanf("%d%d",&x,&k);
		if(k==0)printf("1\n");
		else	printf("%d\n",a[k][x]);
	}
	return 0;
}