#include<cstdio>
using namespace std;
const int NMAX=1000005;
char ciur[NMAX];
int matrix[8][NMAX];
int main(){
    freopen("divprim.in","r",stdin);
    freopen("divprim.out","w",stdout);
    int n,i,nr,k,maxx=-1,prim;
    scanf("%d", &n);
    for(i=1;i<=n;i++){
        scanf("%d%d", &nr, &k);
        if(nr>maxx)
            maxx=nr;
    }
    fclose(stdin);
    freopen("divprim.in","r",stdin);
    for(prim=2;prim<=maxx;prim++){
        if(ciur[prim]==0){
            for(i=prim;i<=maxx;i+=prim)
                ciur[i]++;
        }
        matrix[ciur[prim]][0]++;
        matrix[ciur[prim]][matrix[ciur[prim]][0]]=prim;
    }
    scanf("%d", &n);
    for(i=1;i<=n;i++){
        scanf("%d%d", &nr, &k);
        int j;
        for(j=1;j<=matrix[k][0] && matrix[k][j]<=nr;j++);
        j--;
        if(j<matrix[k][0])
            printf("%d\n", matrix[k][j]);
        else
            if(matrix[k][j]<=nr)
                printf("%d\n", matrix[k][j]);
            else
                printf("0\n");
    }
    return 0;
}