#include <stdio.h>
#define N 1000000
char v[N+1];
int a[8][500000];
void ciur(){
	int i,j;
	for(i=2;i<=N;i++){
		if(!v[i])
			for(j=i;j<=N;j+=i)
				v[j]++;
		a[(int)v[i]][++a[(int)v[i]][0]]=i;
	}
}
int caut(int x,int linie){
	int m,st,dr,i,j;
	st=1;
	dr=a[linie][0];
	while(st<=dr){
		m=(st+dr)/2;
		if(a[linie][m]==x) return m;
		else if(a[linie][m]>x) dr=m-1;
		else st=m+1;
	}
	return st-1;
}
int main(){
	int i,j,n,t,k,sol;
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	scanf("%d",&t);
	ciur();
	for(i=1;i<=t;i++){
		scanf("%d%d",&n,&k);
		sol=caut(n,k);
		if(sol>0)	printf("%d\n",a[k][sol]);
		else printf("0\n");
	}
	return 0;
}