#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif
//#pragma GCC optimize("O3")
#include "dzilib.h"
#include<bits/stdc++.h>
using namespace std;

#define pb push_back

typedef long long ll;
typedef long double ld;
int t, q;
long long c, n;
mt19937_64 rnd(32313131);
int TOT_W[60];
ll gen(ll C, ll mod, ll res) {
    res %= mod;
    if (res < 0) res += mod;
    assert(res < mod && res <= C);
    ll F = rnd() % ((C - res) / mod + 1);
    ll U = F * mod + res;
    assert(U <= C);
    return U;
}
ll TOT_Q = 0;
ll TOT_QQ = 0;
const int maxM = 500'005;
ll F[maxM];

const ll LIM = (1LL << 50) + (ll)1e14 + 1000;
void solve() {
    //init by mod 8
    //I will add my_shift + c / 10
    vector<int> S(8);
    iota(S.begin(), S.end(), 0);
    shuffle(S.begin(), S.end(), rnd);
    c = min(c, (1LL << 50) + 3);
    assert(c + n <= LIM);
    while (true) {
        vector<int> nS;
        shuffle(S.begin(), S.end(), rnd);
        for (auto& it : S) {
            if (nS.empty() && it == S.back()) {
                nS.emplace_back(it);
                break;
            }
            ll T = gen(c, 8, it);
            TOT_QQ += 1;
            int di = Ask(T);
            TOT_Q += 1;
            if (di % 3 != 0) {
            }
            else {
                nS.emplace_back(it);
            }
        }
        swap(S, nS);
        if (S.size() == 1) break;
    }
    ll PW = 8;
    ll cur_res = S[0];
    int ex = 3;
    /*S.resize(4);
    cur_res += 4;
    iota(S.begin(), S.end(), 0);
    shuffle(S.begin(), S.end(), rnd);
    while (true) {
        vector<int> nS;
        for (auto& it : S) {
            ll T = gen(c, 32, it * 8 + cur_res);
            int di = Ask(T);
            TOT_Q += 1;
            if (di % 5 != 0) {
            }
            else {
                nS.emplace_back(it);
            }
        }
        swap(S, nS);
        if (S.size() == 1) break;
    }
    cur_res += S[0] * 8;
    ex += 2;
    PW = 32;*/


    bool FLAG = true;
#ifndef DEBUG
    FLAG = (q <= 820);
#endif
    //q <= 820

    while (PW < n) {
        cur_res += PW / 2;
        cur_res %= PW;
        PW *= 2;
        ex += 1;
        if (PW != 16 && PW != 256 && PW != 65536) {
            ll WW = 0;
            while (true) {
                int z = rnd() % 2;
                bool fnd = false;
                for (int u : {z, 1 - z}) {
                    ll T = gen(c, PW, (cur_res + u * PW / 2));
                    WW += 1;
                    int d = Ask(T);
                    TOT_W[ex] += 1;
                    TOT_Q += 1;
                    bool has_any = false;
                    for (int z = ex + 1; z <= 60; z++) {
                        if (d % z == 0) {
                            if (d / z < maxM && F[d / z] != -1 && F[d / z] <= (LIM / (1LL << (z - 1)))) {
                                //2^{z - 1}
                                has_any = true;
                            }
                        }
                    }
                    if (d % ex != 0) {
                        int any_val = -1;
                        for (int z = ex + 1; z <= 60; z++) {
                            if (d % z == 0 && d / z < maxM && F[d / z] != -1 && F[d / z] <= (LIM / ((1LL << (z - 1))))) {
                                if (any_val == -1) any_val = z;
                                else if (any_val > 0) any_val = -2;
                            }
                        }
                        assert(any_val != -1);
                        if (any_val != -2) {
                            while (ex < any_val) {
                                ex += 1;
                                PW *= 2;
                            }
                            cur_res = T % PW;
                            cur_res %= PW;
                        }
                        else {
                            cur_res += (1 - u) * PW / 2;
                            cur_res %= PW;
                        }
                        fnd = true;
                        break;
                    }
                    else if (!has_any) {
                        cur_res += u * PW / 2;
                        cur_res %= PW;
                        fnd = true;
                        break;
                    }
                }
                if (fnd) break;
            }
        }
        else {
            S.resize(4);
            iota(S.begin(), S.end(), 0);
            shuffle(S.begin(), S.end(), rnd);
            while (true) {
                shuffle(S.begin(), S.end(), rnd);
                vector<int> nS;
                for (auto &it: S) {
                    if (nS.empty() && it == S.back()) {
                        nS.emplace_back(it);
                        break;
                    }
                    ll T = gen(c, PW * 2, it * (PW / 2) + cur_res);
                    int di = Ask(T);
                    TOT_Q += 1;
                    if (di % (ex + 1) != 0) {
                    } else {
                        nS.emplace_back(it);
                    }
                }
                swap(S, nS);
                if (S.size() == 1) break;
            }
            ex += 1;
            cur_res += (PW / 2) * S[0];
            PW *= 2;
        }
    }
    //x + cur_res == PW / 2 mod PW
    ll my_val = (PW / 2 - cur_res) % PW;
    if (my_val <= 0) my_val += PW;
    assert(my_val <= n);
    Answer(my_val);
}
//map<ll,int> F;
vector<ll> primes = {3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 53};
int MX = 0;
void prec(ll num, int pos, ll dv) {
    assert(pos < (int)primes.size());
    assert(dv < maxM);
    if (F[dv] == -1) F[dv] = num;
    else F[dv] = min((ll)F[dv], num);
    MX = max(MX, (int)dv);
    for (ll d = 1; ; d++) {
        if ((ld)num * primes[pos] > LIM + 10) break;
        num *= primes[pos];
        prec(num, pos + 1, dv * (d + 1));
    }
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef DEBUG
    freopen("input.txt", "r", stdin);
#endif
    memset(F, -1, sizeof F);
    prec(1, 0, 1);
//    cout << F.size() << " " << MX << endl;
//    exit(0);
    t = GetT();
    q = GetQ();
    c = GetC();
    n = GetN();
    while (t--) {
        solve();
    }
//    cout << TOT_Q << endl;
    return 0;
}