#include<fstream>
#include<cstring>

using namespace std;
typedef int var;

ifstream fin("divprim.in");
ofstream fout("divprim.out");

var MAX = -1;
var M[1000001][8];
var NR[1000001];

void ciur() {
    for(var i=2; i<=MAX; i++) {
        if(NR[i] == 0) {
            NR[i] = 1;
            for(var j=i+i; j<=MAX; j+=i) {
                NR[j] ++;
            }
        }
        memcpy(M[i], M[i-1], sizeof(M[i]));
        M[i][NR[i]] = i;
    }
}

int main() {
    var t, n, k;
    fin>>t;
    while(t--) {
        fin>>n>>k;
        MAX = max(MAX, n);
    }

    fin.seekg(ios_base::beg);
    ciur();

    fin>>t;
    while(t--) {
        fin>>n>>k;
        fout<<M[n][k]<<'\n';
    }

    return 0;
}