#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);
        if(k!=0){
            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");
        }
        else
            if(nr>=1)
                printf("1\n");
            else
                printf("0\n");
    }
    return 0;
}