#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "dzilib.h"

//#pragma GCC target ("avx2")
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")

#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) ((int) (x).size())
#define pb push_back
#define mp make_pair
#define int long long

using namespace std;
using namespace __gnu_pbds;

template <typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T> inline bool umin(T &a, const T &b) { if(a > b) { a = b; return 1; } return 0; }
template <typename T> inline bool umax(T &a, const T &b) { if(a < b) { a = b; return 1; } return 0; }

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

ll mod = 998244353;
const ll base = 1e6 + 9;
const ll inf = 1e18;
const int MAX = 1e6 + 42;
const int LG = 20;
const int LEN = 17;

struct RNG {
    unsigned int MT[624];
    int index;
    RNG(int seed = 1) {init(seed);}
    void init(int seed = 1) {MT[0] = seed; for(int i = 1; i <  624; ++i) MT[i] = (1812433253UL * (MT[i-1] ^ (MT[i-1] >> 30)) + i); index = 0; }
    void generate() {
        const unsigned int MULT[] = {0, 2567483615UL};
        for (int i = 0; i < 227; ++i){unsigned int y = (MT[i] & 0x8000000UL) + (MT[i+1] & 0x7FFFFFFFUL); MT[i] = MT[i+397] ^ (y >> 1); MT[i] ^= MULT[y&1]; }
        for (int i = 227; i < 623; ++i) {unsigned int y = (MT[i] & 0x8000000UL) + (MT[i+1] & 0x7FFFFFFFUL); MT[i] = MT[i-227] ^ (y >> 1); MT[i] ^= MULT[y&1]; }
        unsigned int y = (MT[623] & 0x8000000UL) + (MT[0] & 0x7FFFFFFFUL); MT[623] = MT[623-227] ^ (y >> 1); MT[623] ^= MULT[y&1];
    }
    unsigned int rand() { if (index == 0) generate(); unsigned int y = MT[index]; y ^= y >> 11; y ^= y << 7  & 2636928640UL; y ^= y << 15 & 4022730752UL; y ^= y >> 18; index = index == 623 ? 0 : index + 1; return y;}
    inline int next() {return rand(); }
    inline int next(int x) {return rand() % x; }
    inline int next(int a, int b) {return a + (rand() % (b - a)); }
    inline double next_double() {return (rand() + 0.5) * (1.0 / 4294967296.0); }
    inline double next_double(double a, double b) {return a + next_double() * (b - a); }
};

static RNG rng;

int phi_minus_one = mod - 2;

class Mint {
    public:
        int x;

    public:
        void norm() {
            x %= mod;
            if(x < 0) x += mod;
        }
        Mint(int a, bool small) {
            x = a;
            if(x >= mod) x -= mod;
            if(x < 0) x += mod;
        }
        Mint() { x = 0; }
        Mint(ll a) {
            x = a % mod;
            if(x < 0) x += mod;
        }
        friend ostream &operator <<(ostream &out, const Mint &a) { out << a.x; return out; }
        friend istream &operator >>(istream &in, Mint &a) { in >> a.x; return in; }
        Mint operator +(const Mint &b) const {
            return Mint(x + b.x, 1);
        }
        Mint operator +(int a) {
            return Mint(x + a, 1);
        }
        Mint operator -(const Mint &b) const {
            return Mint(x - b.x, 1);
        }
        Mint operator -(int a) {
            return Mint(x - a, 1);
        }
        friend Mint operator -(Mint a) {
            return Mint(mod - a);
        }
        Mint operator *(const Mint &b) const {
             return (__int128) x * b.x % mod;
        }
        Mint operator *(int a) {
            return (__int128) x * a % mod;
        }
        Mint& operator +=(const Mint &b) {
            x += b.x;
            if(x >= mod) x -= mod;
            return *this;
        }
        Mint& operator +=(int a) {
            x += a;
            if(x >= mod) x -= mod;
            return *this;
        }
        Mint& operator -=(Mint b) {
            x += mod - b.x;
            if(x >= mod) x -= mod;
            return *this;
        }
        Mint& operator -=(int a) {
            x += mod - a;
            if(x >= mod) x -= mod;
            return *this;
        }
        Mint& operator *=(Mint b) {
            x = (__int128) x * b.x % mod;
            return *this;
        }
        Mint& operator *=(int a) {
            x = (__int128) x * a % mod;
            return *this;
        }
        Mint& operator ++() {
            if(++x == mod) x = 0;
            return *this;
        }
        Mint bpow(ll n) {
            Mint a(x);
            Mint ans(1);
            while(n) {
                if(n & 1) ans *= a;
                n >>= 1;
                a *= a;
            }
            return ans;
        }
        Mint inv() {
            return bpow(phi_minus_one);
        }
        Mint operator /(Mint b) {
            return b.inv() * x;
        }
        Mint operator /(int a) {
            return Mint(a, 1).inv() * x;
        }
        friend Mint operator -(int a, Mint b) {
            Mint res(b - a);
            res.x = mod - res.x;
            if(res.x == mod) res.x = 0;
            return res;
        }
        friend Mint operator +(int a, Mint b) {
            return Mint(b + a);
        }
        friend Mint operator *(int a, Mint b) {
            return Mint(b * a);
        }
        friend Mint operator /(int a, Mint b) {
            return Mint(a, 1) * b.inv();
        }
        Mint operator =(Mint b) {
            x = b.x;
            return b;
        }
        bool operator ==(int a) {
            return (x == a);
        }
        bool operator !=(int a) {
            return !(x == a);
        }
        friend bool operator ==(int a, Mint b) {
            return (b.x == a);
        }
        friend bool operator !=(int a, Mint b) {
            return b.x != a;
        }
};

//vector<Mint> TESTERS = {2}; ///n <= 2e3
//vector<Mint> TESTERS = {2, 3}; ///n <= 1e6
//vector<Mint> TESTERS = {31, 73}; ///n <= 9e6
//vector<Mint> TESTERS = {2, 3, 5}; ///n <= 2e7
//vector<Mint> TESTERS = {2, 3, 5, 7}; ///n <= 3e9
//vector<Mint> TESTERS = {2, 7, 61}; ///n <= 4e9
//vector<Mint> TESTERS = {2, 13, 23, 1662803}; ///n <= 1e12
//vector<Mint> TESTERS = {2, 3, 5, 7, 11}; ///n <= 2e12
//vector<Mint> TESTERS = {2, 3, 5, 7, 11, 13}; ///n <= 3e12
//vector<Mint> TESTERS = {2, 3, 5, 7, 11, 13, 17}; ///n <= 3e14
vector<Mint> TESTERS = {2, 3, 5, 7, 11, 13, 17, 19, 23}; ///n <= 3e18
//vector<Mint> TESTERS = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}; ///n <= 3e23
//vector<Mint> TESTERS = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41}; ///n <= 3e24
///https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

bool prime(ll n) {
    if(n < 2) return 0;
    if(n == 2) return 1;
    if(n & 1 ^ 1) return 0;
    int s = __builtin_ctzll(n - 1);
    ll d = n - 1 >> s; mod = n;
    for(Mint a : TESTERS) {
        if(a == n) continue;
        Mint x = a.bpow(d);
        for(int it = 0; it < s; it++) {
            Mint y = x * x;
            if(y == 1 && x != 1 && x != n - 1) return 0;
            x = y;
        }
        if(x != 1) return 0;
    }
    return 1;
}

ll g(ll x, ll c) {
    return ((__int128) x * x + c) % mod;
}

ll run_Pollard_Rho(ll n) {
    if(n == 1) return 1;
    if(n & 1 ^ 1) return 2;
    ll x = rng.next(2, n);
    ll y = x;
    ll c = rng.next(1, n);
    ll d = 1;
    while(d == 1) {
        x = g(x, c);
        y = g(g(y, c), c);
        d = __gcd(abs(x - y), n);
    }
    return d;
}

ll get_factor(ll n) {
    if(prime(n)) return n;
    while(1) {
        ll c = run_Pollard_Rho(n);
        if(c != n) return c;
    }
}

vector<ll> factor(ll n) {
    if(prime(n)) return {n};
    mod = n;
    vector<ll> ans;
    while(n > 1) {
        ll f = get_factor(n); vector<ll> factorization = factor(f);
        ans.insert(ans.end(), all(factorization)); n /= f;
    }
    sort(all(ans));
    return ans;
}

int get_div(int n) {
    auto f = factor(n); int m = sz(f);
    int ans = 1;
    for(int i = 0; i < m; i++) {
        int j = i;
        while(j < m && f[i] == f[j]) j++; j--;
        ans *= j - i + 2; i = j;
    }
    return ans;
}

int pw(int x, int p) {
    int ans = 1;
    for(int i = 0; i < p; i++) {
        if(ans > inf / x) ans = inf;
        else ans *= x;
    }
    return ans;
}

vector<int> primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541};

int d[MAX];
map<int, int> val;
map<int, int> was;

int ask(int x) {
    if(was[x]) return was[x];
    return was[x] = Ask(x);
}

void solve() {
    int t = GetT();
    int n = GetN();
    int q = GetQ();
    int c = GetC();
    while(t--) {
        was.clear();
        if(n <= 1e6) {
            int h = 0;
            for(int j = 0; j < LEN; j++) h = h * base + ask(j);
            assert(val[h]);
            Answer(val[h]);
            continue;
        }
        int offset = rng.next(0, 1000);
        for(int i = offset;; i++) {
            int d = Ask(i);
            auto check = [&](int x) {
                for(int j = 0; j < 40; j++) {
                    int add = rng.next(0, 1000);
                    if(get_div(x + add) != ask(add)) return 0;
                }
                return 1;
            };
            bool flag = 0;
            for(int siz = 1; siz <= 10; siz++) {
                function<void(int, int, int)> rec = [&](int pos, int x, int left) {
                    if(flag) return;
                    if(pos == siz) {
                        assert(left == 1);
                        if(check(x)) {
                            Answer(x);
                            flag = 1;
                        }
                        return;
                    }
                    if(pos + 1 == siz) {
                        int p = left - 1;
                        p = pw(primes[pos], p);
                        if(x > inf / p) return;
                        x *= p;
                        rec(pos + 1, x, 1);
                    }
                    else {
                        for(int i = 1; i <= left; i++) {
                            if(left % i == 0) {
                                int p = i - 1;
                                p = pw(primes[pos], p);
                                if(x > inf / p) continue;
                                rec(pos + 1, x * p, left / i);
                            }
                        }
                    }
                };
                rec(0, 1, d);
                if(flag) break;
            }
            if(flag) break;
        }
    }
}

signed main() {
    for(int i = 1; i < MAX; i++) {
        for(int j = i; j < MAX; j += i) d[j]++;
    }
    for(int i = 1; i <= 1000000; i++) {
        int h = 0;
        for(int j = 0; j < LEN; j++) h = h * base + d[i + j];
        assert(!val[h]);
        val[h] = i;
    }
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int ttt = 1;
//    cin >> ttt;
    while(ttt--) {
        solve();
    }
}