#include<stdio.h>

#define INF 20000000

int A[1000001];
int best[1000001][8];
int N;
int T;
int K;
int j;
int MAX = -INF;

void erathosteness(int N)
{
	for(int i=2;i<=N;i++)
		if(!A[i])
			for(int j=i;j<=N;j+=i)
				A[j] ++;
}

int main()
{
	FILE *f = fopen("divprim.in","r");
	FILE *g = fopen("divprim.out","w");
	
	fscanf(f,"%d",&T);
	for(int i=1;i<=T;i++)
	{
		fscanf(f,"%d %d",&N,&K);
		if(MAX<N)
			MAX = N;
	}
	erathosteness(MAX);
	for(int i=1;i<=MAX;i++)
		for(int j=1;j<=7;j++)
		{
			best[i][j] = best[i-1][j];
			if(A[i] == j)
				best[i][j] = i;
		}
	rewind(f);
	fscanf(f,"%d",&T);
	for(int i=1;i<=T;i++)
	{
		fscanf(f,"%d %d",&N,&K);
		fprintf(g,"%d\n",best[N][K]);
	}
	
	fclose(g);
	fclose(f);
}