#include<fstream.h>
#define nmax 1000001
#define mmax 10001

int sol[nmax];
long t,i,j,a,b,max,x[18][mmax],poz;

int BS(long b,int k)
{
	int lo, hi, mid, last = 0;

	for (lo = 1, hi = x[b][0]; lo <= hi; )
	{
		mid = lo + (hi-lo) / 2;
		if (x[b][mid] <= k) last = mid, lo = mid+1;
		else hi = mid-1;
	}
	return last;
}

int main()
{
	ifstream f("divprim.in");
	ofstream g("divprim.out");


	f>>t;

	for(i=1;i<=t;i++)
		{ f>>a>>b;
		  if(a>max)	max=a;
		}
	for(i=2;i<=max;i++)
		if(sol[i]==0)
			for(j=i;j+i<=max;j=j+i)
				sol[j]++;
	f.close();

	f.open("divprim.in");

	for(i=2;i<=max;i++)
		{
			x[sol[i]][x[sol[i]][0]+1]=i;
			x[sol[i]][0]++;
		}

	f>>t;
	for(i=1;i<=t;i++)
		{
		f>>a>>b;
		int y=BS(b,a);
		if(y!=0)
			g<<x[b][y]<<"\n";
		else
                	g<<"0\n";


		}
	return 0;
}