#include<fstream>
#include<cstring>
#include<vector>

using namespace std;
typedef int var;

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

var MAX = -1;
vector<var> L[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] ++;
            }
        }
        L[NR[i]].push_back(i);
    }
}

var lb(vector<var> &V, var val) {
    var i, poz=0;
    for(i=1; i<=V.size()-1;i<<=1);
    for(i>>=1; i; i>>=1) {
        if(poz + i < V.size() && V[poz+i] <= val) {
            poz += i;
        }
    }
    return V[poz];
}

int main() {
    var t, n, k;
    fin>>t;
    for(var i=0; i<=7; i++) {
        L[i].push_back(0);
    }
    while(t--) {
        fin>>n>>k;
        MAX = max(MAX, n);
    }

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

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

    return 0;
}