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
#include <iostream>
#include <unordered_map>
#include <vector>
#include "dzilib.h"

using namespace std;

unordered_map<long long, long long> cache;

long long askCache(long long y) {
    long long dividers = cache[y];
    if (dividers > 0) {
        return dividers;
    }
    dividers = Ask(y);
    cache[y] = dividers;
    return dividers;
}

pair<long long, bool> filterCandidates(long long power, long long base, vector<long long> &candidates, bool first) {
    vector<long long>::iterator iter;
    int i = 0;
    while (candidates.size() > 1) {
        iter = candidates.begin();
        while (iter != candidates.end()) {
            long long dividers = askCache(*iter + i * base);
            if (!first && dividers == power + 1) {
                return {*iter, true};
            } else if (dividers % power == 0LL) {
                iter++;
            } else {
                iter = candidates.erase(iter);
            }
        }
        i++;
    }
    long long result = candidates[0];
    candidates.clear();
    return {result, false};
}

long long solve() {
    long long power = 3LL;
    long long base = 8LL;
    vector<long long> candidates;
    for (int i = 0; i < 8; i++) {
        candidates.push_back(i);
    }
    while (true) {
        auto [y, finish] = filterCandidates(power, base, candidates, power == 3LL);
        if (finish) {
            return base - y;
        }
        y -= base / 2;
        if (y < 0) {
            y += base;
        }
        candidates.push_back(y);
        candidates.push_back(y + base);
        power++;
        if ((power & (power - 1)) == 0) {
            candidates.push_back(y + 2 * base);
            candidates.push_back(y + 3 * base);
            power++;
            base *= 2;
        }
        base *= 2;
    }
}

int main() {
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t = GetT();
    for (int i = 0; i < t; i++) {
        cache.clear();
        Answer(solve());
    }
}