1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include "dzilib.h"
#include <unordered_map>
#include <unordered_set>
using namespace std;

unordered_map<long long, long long> answers;
long long ask(long long y) {
  if (!answers.contains(y)) {
    answers[y] = Ask(y);
  }
  return answers[y];
}

void testcase() {
  answers.clear();
  unordered_set<long long> candidates;
  for (int i = 0; i < 8; ++i) {
    long long ans = ask(i);
    if (ans % 3 == 0) {
      candidates.insert(i);
    }
  }
  int round = 0;
  while (size(candidates) > 1) {
    ++round;
    unordered_set<long long> newCandidates;
    for (auto c : candidates) {
      if (ask(c + 8 * round) % 3 == 0) {
        newCandidates.insert(c);
      }
    }
    candidates = std::move(newCandidates);
  }
  long long y = *begin(candidates);
  int power = 2;
  int maxround = 0;
  for (;;) {
    if (ask(y) == power + 1) {
      break;
    }
    if (power == 2 || power == 6 || power == 14 || power == 30) {
      candidates.clear();
      long long c1 = y + (1LL << power), c2 = y + 3 * (1LL << power), c3 = y + 5 * (1LL << power), c4 = y + 7 * (1LL << power);
      if (c1 > 1LL << (power + 3)) {
        c1 -= 1LL << (power + 3);
      }
      if (c2 > 1LL << (power + 3)) {
        c2 -= 1LL << (power + 3);
      }
      if (c3 > 1LL << (power + 3)) {
        c3 -= 1LL << (power + 3);
      }
      if (c4 > 1LL << (power + 3)) {
        c4 -= 1LL << (power + 3);
      }
      ++++power;
      auto ans1 = ask(c1);
      auto ans2 = ask(c2);
      auto ans3 = ask(c3);
      auto ans4 = ask(c4);
      if (ans1 % (power + 1) == 0) {
        candidates.insert(c1);
      }
      if (ans2 % (power + 1) == 0) {
        candidates.insert(c2);
      }
      if (ans3 % (power + 1) == 0) {
        candidates.insert(c3);
      }
      if (ans4 % (power + 1) == 0) {
        candidates.insert(c4);
      }
    } else {
      candidates.clear();
      long long c1 = y + (1LL << power), c2 = y + 3 * (1LL << power);
      if (c1 > 1LL << (power + 2)) {
        c1 -= 1LL << (power + 2);
      }
      if (c2 > 1LL << (power + 2)) {
        c2 -= 1LL << (power + 2);
      }
      ++power;
      auto ans1 = ask(c1);
      auto ans2 = ask(c2);
      if (ans1 % (power + 1) == 0) {
        candidates.insert(c1);
      }
      if (ans2 % (power + 1) == 0) {
        candidates.insert(c2);
      }
    }
    int round = 0;
    while (size(candidates) > 1) {
      ++round;
      unordered_set<long long> newCandidates;
      for (auto c : candidates) {
        if (ask(c + (1LL << (power + 1)) * round) % (power + 1) == 0) {
          newCandidates.insert(c);
        }
      }
      candidates = std::move(newCandidates);
    }
    y = *begin(candidates);
  }
  Answer((1LL << power) - y);
}

int main() {
  int t = GetT();
  for (int i = 0; i < t; ++i) {
    testcase();
  }
}