#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <unordered_set>
#include <vector>
#include <climits>
using namespace std;

using ll = long long;
using ul = unsigned long long;
using db = long double;
using pi = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
using vpi = vector<pi>;
using pl = pair<ll, ll>;
using vpl = vector<pl>;
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define x first
#define y second

template<class T> using V = vector<T>; 
template<class T, size_t SZ> using AR = array<T,SZ>; 

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define each(a,x) for (auto& a: x)
 
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define rep(i,a,b) for(int i = (a); i < (b); i++)
#define per(i,a,b) for(int i = (b) - 1; i >= (a); i--)

#ifdef LOCAL 
template<class A, class B> auto& operator<<(auto &o, pair<A, B> p) { return o << '(' << p.x << ", " << p.y << ')'; }
auto& operator<<(auto& o, auto a) {
    o << "{";
    for (auto b : a) o << b << ", ";
    return o << "}";
}
void dump(auto... x) { ((cerr << x << ", "), ...) << "\n"; }
#define debug(x...) cerr << "[" #x "]: ", dump(x)
#else
#define debug(...) ;
#endif

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<class T> int lwb(V<T>& a, const T& b) { return int(lb(all(a),b)-bg(a)); }
template<class T> int upb(V<T>& a, const T& b) { return int(ub(all(a),b)-bg(a)); }
template<class T> void remDup(vector<T>& v) { sort(all(v)); v.erase(unique(all(v)),end(v)); }

#include "dzilib.h"

const int MAX_PRIME = 3e6;
vl primes;
bool is_prime[MAX_PRIME];
int tau_preproc[MAX_PRIME];

void euclid() {
    fill(is_prime, is_prime + MAX_PRIME, true);
    is_prime[0] = is_prime[1] = false;
    tau_preproc[1] = 1;

    for (ll p = 2; p < MAX_PRIME; p++) {
        tau_preproc[p] += 2; // 1, p
        if (is_prime[p]) {
            primes.pb(p);
            for (ll q = p * p; q < MAX_PRIME; q += p) {
                is_prime[q] = false;
            }
        }
        for (ll q = 2 * p; q < MAX_PRIME; q += p) {
            tau_preproc[q]++;
        }
    }
}

ll binpow(ll p, ll x) {
    ll res = 1;
    while (x) {
        if (x & 1) res *= p;
        p *= p;
        x /= 2;
    }
    return res;
}

ll tau(ll x) {
    if (x < MAX_PRIME) return tau_preproc[x];
    ll res = 1;
	for (ll i : primes) {
        if (i * i > x) break;
		ll mult = 1;
		while (x % i == 0) {
			mult++;
			x /= i;
        }
		res *= mult;
	}
    if (x > 1) res *= 2;
    return res;
}

int t, q;
ll n, c;

// mt19937_64 rng(8423);
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int MAXN_SMALL = 1e6;

bool test_case_1_2() {
    static bool initialized = false;
    static constexpr int num_initial_asks = 16;
    using Arr = array<int, num_initial_asks>;
    static Arr initial_asks;
    static map<Arr, vi> m;
    
    if (!initialized) {
        initialized = true;
        initial_asks[0] = 0;
        rep(i,1,num_initial_asks) {
            initial_asks[i] = rng() % (MAX_PRIME / 2) + 1;
        }
        rep(i,1,MAXN_SMALL+1) {
            Arr cur;
            rep(j,0,num_initial_asks) {
                int x = i + initial_asks[j];
                cur[j] = (int)tau(x);
            }
            m[cur].pb(i);
        }
    }

    Arr cur;
    rep(i,0,num_initial_asks) {
        cur[i] = (int)Ask(initial_asks[i]);
    }

    auto v = m[cur];

    if (v.empty()) {
        return false;
    }

    while (sz(v) > 1) {
        auto asked = rng() % c;
        auto tau_got = Ask(asked);
        rep(i,0,sz(v)) {
            auto actual_value = asked + v[i];
            if (tau_got != tau(actual_value)) {
                swap(v[i], v.back());
                v.pop_back();
                i--;
            }
        }
    }

    Answer(v[0]);
    return true;
}

const ll MAX_C = 1e17;

void test_case_up_6(bool randomize_start = false) {
    static vi next_tau_values = {};
    static int primes_to_check_per_valid_guess = 0;
    static int second_primes_to_check = 0;
    static int tau_feasibility_index = 18;
    // static int first_check_threshold = 5;
    // static int second_check_threshold = 9;
    static int first_check_threshold = 3;
    static int second_check_threshold = 5;

    if (next_tau_values.empty()) {
        if (c == MAX_C) {
            // next_tau_values = {1, 5, 11, 17, 23, 29, 31, 37, 43, 47, 53};
            // next_tau_values = {1, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53};
            // next_tau_values = {1, 3, 5, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, 51};
            // next_tau_values = {1, 5, 7, 11, 13, 15, 17, 19, 23, 27, 31, 35, 39, 43, 47, 51};
            // next_tau_values = {1, 5, 11, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53};
            next_tau_values = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53};
            // next_tau_values = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 23, 27, 31, 35, 39, 43, 47, 51, 53};
            primes_to_check_per_valid_guess = 2;
            second_primes_to_check = 1;
        }
        else {
            // next_tau_values = {1, 5, 11, 17, 23, 29, 31};
            next_tau_values = {1, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41};
            primes_to_check_per_valid_guess = 10;
            // tau_feasibility_index = 
        }
    }
    ll offset = 0;
    rep(i,0,sz(next_tau_values) - 1) {
        ll cur_tau = next_tau_values[i];
        ll nxt_tau = next_tau_values[i+1];
        ll pow_multiplier = binpow(2, cur_tau - 1);
        ll random_start = 1;
        if (randomize_start) {
            random_start = 1 + (rng() % 8) * 8;
        }

        for (ll x = random_start;; x++) {
            if ((x >= 8 + random_start && c == MAX_C && nxt_tau > 5) || (x >= 128 + random_start)) {
                // mega jajco, trzeba wszystko od nowa
                // debug("jajco 1", x - random_start);
                test_case_up_6(true);
                return;
            }
            if ((c == MAX_C && nxt_tau <= 5 && x >= 32 + random_start)) {
                // debug("jajco 1.1", x - random_start);
                test_case_up_6(true);
                return;
            }
            ll to_ask = offset + pow_multiplier * x;
            if (to_ask >= c) {
                // mega jajco, trzeba wszystko od nowa
                // debug("jajco 2");
                test_case_up_6(true);
                return;
            }

            ll got_tau = Ask(to_ask);
            if (got_tau == nxt_tau) {
                // shortcut
                ll got_value = binpow(2, got_tau - 1);
                ll result = got_value - to_ask;
                // debug("true git");
                if (result > 0) {
                    if (result < MAXN_SMALL) {
                        test_case_1_2();
                        return;
                    }
                    Answer(result);
                    return;
                }
            }

            per(j,0,sz(next_tau_values)) {
                if (!is_prime[next_tau_values[j]]) continue;
                if (j > i && got_tau % next_tau_values[j] == 0) {
                    nxt_tau = next_tau_values[j];
                    i = j - 1;
                    break;
                }
            }

            if (got_tau % nxt_tau == 0) {
                ll check_multiplier = binpow(2, 51);
                if (c < MAX_C) {
                    check_multiplier = binpow(2, 36);
                    bool git = true;
                    
                    for (ll check_iter = 1; check_iter <= primes_to_check_per_valid_guess; check_iter++) {
                        ll to_check_ask = to_ask + check_multiplier * check_iter;
                        if (to_check_ask >= c) {
                            break;
                        }
                        ll got_check_tau = Ask(to_check_ask);
                        if (got_check_tau % nxt_tau != 0) {
                            git = false;
                            break;
                        }
                    }

                
                    if (!git) {
                        continue;
                    }
                }
                
                if (i < first_check_threshold) {
                    bool git = true;
                    
                    for (ll check_iter = 1; check_iter <= primes_to_check_per_valid_guess; check_iter++) {
                        ll to_check_ask = to_ask + check_multiplier * check_iter;
                        if (to_check_ask >= c) {
                            break;
                        }
                        ll got_check_tau = Ask(to_check_ask);
                        if (got_check_tau % nxt_tau != 0) {
                            git = false;
                            break;
                        }
                    }

                    if (!git) {
                        continue;
                    }
                }
                else if (i < second_check_threshold) {
                    bool git = true;
                    
                    for (ll check_iter = 1; check_iter <= second_primes_to_check; check_iter++) {
                        ll to_check_ask = to_ask + check_multiplier * check_iter;
                        if (to_check_ask >= c) {
                            break;
                        }
                        ll got_check_tau = Ask(to_check_ask);
                        if (got_check_tau % nxt_tau != 0) {
                            git = false;
                            break;
                        }
                    }

                    if (!git) {
                        continue;
                    }
                }

                if (got_tau / nxt_tau == 2 && i > tau_feasibility_index) {
                    for (ll P : {3, 5, 7}) {
                        ll dopelnienie = 1;
                        if (P == 5) {
                            dopelnienie = 3;
                        }
                        if (P == 11) {
                            dopelnienie = 5;
                        }
                        ll expected_tau = nxt_tau + 2;
                        if (P > 3) expected_tau++; // dopelnienie do 8
                        if (P == 11) expected_tau++; // do 16

                        ll hope = dopelnienie * binpow(2, nxt_tau - 1);
                        ll cur_to_ask = to_ask + hope;
                        
                        if (cur_to_ask >= c || cur_to_ask < 0) break;

                        ll response = Ask(cur_to_ask);

                        if (response == expected_tau) {
                            ll final_pow2 = binpow(2, expected_tau - 1);
                            ll final_result = final_pow2 - cur_to_ask;
                            Answer(final_result);
                            return;
                        }
                    }
                }
                else if (got_tau / nxt_tau == 3 && i > tau_feasibility_index) {
                    for (ll P : {3, 5}) {
                        ll dopelnienie = 7; // 16 - 9, 32 - 25
                        ll expected_tau = nxt_tau + 4;
                        if (P == 5) expected_tau++;
                        ll hope = dopelnienie * binpow(2, nxt_tau - 1);
                        ll cur_to_ask = to_ask + hope;
                        if (cur_to_ask >= c || cur_to_ask < 0) break;
                        ll response = Ask(cur_to_ask);
                        if (response == expected_tau) {
                            ll final_pow2 = binpow(2, expected_tau - 1);
                            ll final_result = final_pow2 - cur_to_ask;
                            Answer(final_result);
                            return;
                        }
                    }
                }

                offset = to_ask;
                break;
            }
        }
    }

    return test_case_up_6(true);
}

const int N_FOR_CASE_1_2 = 1e6;

void testcase() {
    if (n <= N_FOR_CASE_1_2) {
        test_case_1_2();
        return;
    }
    test_case_up_6();
}

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);

    cerr << fixed << setprecision(2);

    euclid();

    t = GetT();
    n = GetN();
    q = GetQ();
    c = GetC();

    while (t--) {
        testcase();
    }

    return 0;
}