#include <stdio.h>
#define N 1000005
#define M 400000
char v[N];
int a[8][M];
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 x1,int x2){
	int st=1,dr=a[x2][0],m,i;
	while(st<=dr){
		m=(st+dr)/2;
		if(a[x2][m]<x1) st=m+1;
		else if(a[x2][m]>x1) dr=m-1;
		else return m;
	}
	return st-1;
}
	
int main()
{ 
	int i,j,x,y,z,sol,n;
	FILE*f=fopen("divprim.in","r");
	FILE*g=fopen("divprim.out","w");
	ciur();
	fscanf(f,"%d",&n);
	for(i=1;i<=n;i++){
		fscanf(f,"%d%d",&x,&y);
		sol=caut(x,y);
		if(sol==0) fprintf(g,"0\n");
		else fprintf(g,"%d\n",a[y][sol]);
	}
return 0;
}