#include "dzilib.h"
#include <bits/stdc++.h>
#include <chrono>
using namespace std;
#define _upgrade ios_base::sync_with_stdio(0), cout.setf(ios::fixed), cout.precision(10), cin.tie(0), cout.tie(0);
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(c) (c).begin(), (c).end()
#define sz(X) (int)((X).size())
#ifdef LOCAL
ostream &operator<<(ostream &out, string str) {
   for (char c : str)
      out << c;
   return out;
}
template <class L, class R> ostream &operator<<(ostream &out, pair<L, R> p) { return out << "(" << p.st << ", " << p.nd << ")"; }
template <class L, class R, class S> ostream &operator<<(ostream &out, tuple<L, R, S> p) {
   auto &[a, b, c] = p;
   return out << "(" << a << ", " << b << ", " << c << ")";
}
template <class T> auto operator<<(ostream &out, T a) -> decltype(a.begin(), out) {
   out << '{';
   for (auto it = a.begin(); it != a.end(); it = next(it))
      out << (it != a.begin() ? ", " : "") << *it;
   return out << '}';
}
void dump() { cerr << "\n"; }
template <class T, class... Ts> void dump(T a, Ts... x) {
   cerr << a << ", ";
   dump(x...);
}
#define debug(...) cerr << "[" #__VA_ARGS__ "]: ", dump(__VA_ARGS__)
#else
#define debug(...) 42
#endif
typedef unsigned long long ull;
#define int long long
typedef long long ll;

// Source: https://judge.yosupo.jp/submission/189742
namespace FACTOR {

   // ---- gcd ----

   uint64_t gcd_stein_impl(uint64_t x, uint64_t y) {
      if (x == y) {
         return x;
      }
      const uint64_t a = y - x;
      const uint64_t b = x - y;
      const int n = __builtin_ctzll(b);
      const uint64_t s = x < y ? a : b;
      const uint64_t t = x < y ? x : y;
      return gcd_stein_impl(s >> n, t);
   }

   uint64_t gcd_stein(uint64_t x, uint64_t y) {
      if (x == 0) {
         return y;
      }
      if (y == 0) {
         return x;
      }
      const int n = __builtin_ctzll(x);
      const int m = __builtin_ctzll(y);
      return gcd_stein_impl(x >> n, y >> m) << (n < m ? n : m);
   }

   // ---- is_prime ----

   uint64_t mod_pow(uint64_t x, uint64_t y, uint64_t mod) {
      uint64_t ret = 1;
      uint64_t acc = x;
      for (; y; y >>= 1) {
         if (y & 1) {
            ret = __uint128_t(ret) * acc % mod;
         }
         acc = __uint128_t(acc) * acc % mod;
      }
      return ret;
   }

   bool miller_rabin(uint64_t n, const std::initializer_list<uint64_t> &as) {
      return std::all_of(as.begin(), as.end(), [n](uint64_t a) {
         if (n <= a) {
            return true;
         }

         int e = __builtin_ctzll(n - 1);
         uint64_t z = mod_pow(a, (n - 1) >> e, n);
         if (z == 1 || z == n - 1) {
            return true;
         }

         while (--e) {
            z = __uint128_t(z) * z % n;
            if (z == 1) {
               return false;
            }
            if (z == n - 1) {
               return true;
            }
         }

         return false;
      });
   }

   bool is_prime(uint64_t n) {
      if (n == 2) {
         return true;
      }
      if (n % 2 == 0) {
         return false;
      }
      if (n < 4759123141) {
         return miller_rabin(n, {2, 7, 61});
      }
      return miller_rabin(n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
   }

   // ---- Montgomery ----

   class Montgomery {
      uint64_t mod;
      uint64_t R;

    public:
      Montgomery(uint64_t n) : mod(n), R(n) {
         for (size_t i = 0; i < 5; ++i) {
            R *= 2 - mod * R;
         }
      }

      uint64_t fma(uint64_t a, uint64_t b, uint64_t c) const {
         const __uint128_t d = __uint128_t(a) * b;
         const uint64_t e = c + mod + (d >> 64);
         const uint64_t f = uint64_t(d) * R;
         const uint64_t g = (__uint128_t(f) * mod) >> 64;
         return e - g;
      }

      uint64_t mul(uint64_t a, uint64_t b) const { return fma(a, b, 0); }
   };

   // ---- Pollard's rho algorithm ----

   uint64_t pollard_rho(uint64_t n) {
      if (n % 2 == 0) {
         return 2;
      }
      const Montgomery m(n);

      constexpr uint64_t C1 = 1;
      constexpr uint64_t C2 = 2;
      constexpr uint64_t M = 512;

      uint64_t Z1 = 1;
      uint64_t Z2 = 2;
   retry:
      uint64_t z1 = Z1;
      uint64_t z2 = Z2;
      for (size_t k = M;; k *= 2) {
         const uint64_t x1 = z1 + n;
         const uint64_t x2 = z2 + n;
         for (size_t j = 0; j < k; j += M) {
            const uint64_t y1 = z1;
            const uint64_t y2 = z2;

            uint64_t q1 = 1;
            uint64_t q2 = 2;
            z1 = m.fma(z1, z1, C1);
            z2 = m.fma(z2, z2, C2);
            for (size_t i = 0; i < M; ++i) {
               const uint64_t t1 = x1 - z1;
               const uint64_t t2 = x2 - z2;
               z1 = m.fma(z1, z1, C1);
               z2 = m.fma(z2, z2, C2);
               q1 = m.mul(q1, t1);
               q2 = m.mul(q2, t2);
            }
            q1 = m.mul(q1, x1 - z1);
            q2 = m.mul(q2, x2 - z2);

            const uint64_t q3 = m.mul(q1, q2);
            const uint64_t g3 = gcd_stein(n, q3);
            if (g3 == 1) {
               continue;
            }
            if (g3 != n) {
               return g3;
            }

            const uint64_t g1 = gcd_stein(n, q1);
            const uint64_t g2 = gcd_stein(n, q2);

            const uint64_t C = g1 != 1 ? C1 : C2;
            const uint64_t x = g1 != 1 ? x1 : x2;
            uint64_t z = g1 != 1 ? y1 : y2;
            uint64_t g = g1 != 1 ? g1 : g2;

            if (g == n) {
               do {
                  z = m.fma(z, z, C);
                  g = gcd_stein(n, x - z);
               } while (g == 1);
            }
            if (g != n) {
               return g;
            }

            Z1 += 2;
            Z2 += 2;
            goto retry;
         }
      }
   }

   void factorize_impl(uint64_t n, std::vector<uint64_t> &ret) {
      if (n <= 1) {
         return;
      }
      if (is_prime(n)) {
         ret.push_back(n);
         return;
      }

      const uint64_t p = pollard_rho(n);

      factorize_impl(p, ret);
      factorize_impl(n / p, ret);
   }

   std::vector<uint64_t> factorize(uint64_t n) {
      std::vector<uint64_t> ret;
      factorize_impl(n, ret);
      std::sort(ret.begin(), ret.end());
      return ret;
   }

   int d0(uint64_t n) {
      auto D = factorize(n);
      std::map<int, int> M;
      for (auto d : D)
         M[d]++;
      int res = 1;
      for (auto [_, cnt] : M)
         res *= (cnt + 1);
      return res;
   }

} // namespace FACTOR

#define int long long
namespace RNG {
   mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
   uniform_int_distribution<ull> distr(0, 1e18);
   auto my_rand = bind(distr, gen); // my_rand() zwraca teraz liczbe z przedzialu [a, b]

   ull get_rand(ull C) { return my_rand() % C; }
   ull get_rand(ull C, ull S, int k) { return (get_rand(C >> k) << k) ^ S; }

} // namespace RNG

int cnt = 0;
map<ll, ll> M;
ll ask(ll c, int C) {
   assert(c <= C);
   if (M.count(c))
      return M[c];
   cnt++;
   return M[c] = Ask(c);
   // FACTOR::d0(hidden_x + c);
}

set<int> dont_need = {30, 36, 40, 42, 46, 52};
multiset<int> more = {2, 2, 2, 2, 2, 2, 4, 4, 6, 9, 9, 13, 14, 19, 19, 27, 29, 39, 44};
vector<int> rel = {2, 4, 6, 9, 10, 12, 13, 14, 16, 18, 19, 20, 21, 22, 24, 25, 27, 28, 29, 30, 32, 33, 34, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 48, 49, 50, 51, 52, 54};

bool verify(int c, int pw, int C) {
   auto good = [pw, C](int c) { return ask(c, C) % (pw + 1) == 0; };
   assert(good(c));
   const int level = 1 + more.count(pw) - dont_need.count(pw) + (C < 1e16);
   rep(i, level) if (!good(c + (i + 1) * (1LL << (pw + 1)))) return false;
   return true;
}

int get(int c, int d0, int cur, int C) {
   for (int i : rel)
      if (i > cur and d0 % (i + 1) == 0 and (4ll << i) < C) {
         if (verify(c, i, C))
            return i;
         else
            return -1;
      }
   return -1;
}

bool check(int x) {
   for (auto [c, d] : M)
      if (FACTOR::d0(x + c) != d)
         return false;
   return true;
}

vector<int> check(vector<int> X) {
   vector<int> good;
   for (auto x : X)
      if (check(x))
         good.push_back(x);

   //    debug(good);
   assert(sz(good));
   return good;
}

int check(int N, int t, int pw) {
   const int LIMIT = 100;
   int L = (1ll << pw) - 1;
   int x = (1ll << pw) - (t & L);
   assert(x <= N);
   vector<int> X = {x};
   while (sz(X) <= LIMIT and X.back() <= N)
      X.push_back(X.back() + (1ll << pw));
   //    debug(X);
   if (sz(X) > LIMIT)
      return -1;
   auto res = check(X);
   if (sz(res) == 1)
      return res[0];
   else
      return -1;
}

int jazda(int N, int C) {
   M.clear();
   auto t = RNG::get_rand(C / 5);
   int pw = -1;
   int res = -1;
   debug("START", N, C);
   while (res == -1) {
      if ((1ll << pw) > N * 2)
         assert(false);

      int incr = pw == -1 ? 1 : (2ll << pw);
      int cur = pw;
      pw = -1;
      while (pw == -1) {
         t += incr;
         auto d0 = ask(t, C);
         pw = get(t, d0, cur, C);
         debug(d0, pw);
      }
      debug(t, pw);

      res = check(N, t, pw);
      t += (1ll << pw);
   }
   return res;
}

int32_t main() {
   int T = GetT();
   int N = GetN();
   int _Q = GetQ();
   int C = GetC();
   while (T--) {
      M.clear();
      auto res = jazda(N, C);
      Answer(res);
   }
}