#include<stdio.h>
#define N 1000005
#define M 400000
char c[N];
int a[8][M];
void ciur(){
	c[1]=1;
	for(int i=2;i<N;++i){
		if(!c[i]){
			++c[i];
			for(int j=i+i;j<N;j+=i)
				++c[j];
		}
		a[(int)c[i]][ ++a[(int)c[i]][0] ] = i;
		/*
		++a[c[i]][0];
		a[c[i]] [a[c[i]][0]]=i;
		*/
	}
}
int caut(int nrd,int x){
	int m,p=1,u=a[nrd][0];
	while(p<u){
		m=(p+u)/2;
		if(x<=a[nrd][m])
			u=m;
		else
			p=m+1;
	}
	if(a[nrd][p]>x)
		return p-1;
	return p;
}
int main(){
	freopen("divprim.in","r",stdin);
	freopen("divprim.out","w",stdout);
	ciur();
	int t,n,k,poz;
	scanf("%d",&t);
	while(t){
		scanf("%d%d",&n,&k);
		poz=caut(k,n);
		if(poz==0)
			printf("0\n");
		else
			printf("%d\n",a[k][poz]);
		--t;
	}
	fclose(stdin);
	fclose(stdout);
	return 0;
}