// Przykładowe niepoprawne rozwiązanie do zadania Dzielniki.
#include "dzilib.h"

#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (b); i >= (a); i--)
#define SZ(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define st first
#define nd second
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
auto &operator<<(auto &o, pair<auto, auto> p) {
    return o << "(" << p.st << ", " << p.nd << ")";
}
auto operator<<(auto &o, auto x)->decltype(end(x), o) {
    o << "{"; int i=0; for(auto e: x) o << ", " + 2*!i++ << e;
    return o << "}";
}
#define deb(x...) cerr << "[" #x "]: ", [](auto...$) { ((cerr<<$<<"; "),...) << endl; }(x)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll ops = 0;
ll C;

unsigned long long los(ll a, ll b){
    unsigned long long tmp = rng();
    unsigned long long res = (tmp << 32) + rng();
    return a + res % (b - a + 1);
}

vector<ll> rozklad(ll x){
    vector<ll> ans;
    for(ll i=2;i*i<=x;i++){
        while(x % i == 0){
            ans.pb(i);
            x /= i;
        }
    }
    if(x > 1) ans.pb(x);
    return ans;
}

ll divisorCount(ll x){
    vector<ll> ans;
    for(ll i=2;i*i<=x;i++){
        while(x % i == 0){
            ans.pb(i);
            x /= i;
        }
    }
    if(x > 1) ans.pb(x);
    ll cnt = 1;
    rep(i, 0, SZ(ans) - 1){
        int j = i;
        while(j + 1 < SZ(ans) && ans[j + 1] == ans[j]) j += 1;
        cnt *= (j - i + 2);
        i = j;
    }
    return cnt;
}

map<ll, int> cached;
ll query(ll c){
    if(cached.count(c)) return cached[c];
    ops += 1;
    ll tmp = Ask(c);
    return cached[c] = tmp;
}

bool sprawdz(ll cand){
    if(cand <= 0) return false;
    for(auto [c, res] : cached){
        if(divisorCount(cand + c) != res) return false;
    }
    Answer(cand);
    return true;
}
ll male;

void skoncz(){
    cout << ops << endl;
}

ll duzaLosowa(){
    return los(1, C / 1000);
}


vector<ll> divisors(ll x){
    vector<ll> ans;
    for(ll i=1;i*i<=x;i++){
        if(x % i == 0){
            ans.pb(i);
            if(i * i != x) ans.pb(x/i);
        }
    }
    return ans;
}

bool in(ll x, vector<ll> a){
    for(ll y : a){
        if(x == y) return true;
    }
    return false;
}

bool szukaj(ll offset, int twos, bool canFail = false, bool duze = false){
    //deb(twos);
    if(offset == -1){
        ll added = duzaLosowa();
        vector<int> res(2, 0);
        rep(i, 0, 1){
            res[i] = query(i + added);
        }
        ll sum[2] = {0, 0};
        rep(i, 0, 1) sum[i % 2] += res[i];
        ll start = added;
        if(sum[1] < sum[0]) start += 1;
        auto ok = szukaj(start, 0);
        if(!ok) return szukaj(-1, 0);
        return true;
    }
    ll akt = query(offset);
    duze |= (rozklad(akt).back() >= 5);
    if(duze){
        auto dziel = divisors(akt);
        ll mx = -1;
        for(auto x : dziel) mx = max(mx, x);
        while(!in(twos + 1, dziel) && twos + 1 < mx){
            twos += 1;
        }
    }
    if(twos >= 58) return false;
    if(akt == twos + 1){
        if(sprawdz((1LL << twos) - offset)){
            return true;
        }
        return false;
    }

    if((1LL << twos) >= C / 1000 * 2){
        if(akt == (twos + 1) * 2){
            if(sprawdz((1LL << twos) * 3 - offset)){
                return true;
            }
        }
        return false;
    }

    ll power = (1LL << twos);
    ll want = twos + 2;

    if(twos <= 17){
        ll go1 = query(offset + power);
        ll go2 = query(offset + power + power + power);

        if(go1 % want != 0 && go2 % want != 0){
            if(canFail) return false;
            else return szukaj(-1, 0);
        }
        want = twos + 2;
        if(go1 % want != go2 % want){
            if(go1 % want == 0){
                return szukaj(offset + power, twos + 1, duze);
            }
            else{
                return szukaj(offset + power + power + power, twos + 1, duze);
            }
        }
        ll lewoW = 0;
        ll prawoW = 0;
        go1 /= want;
        go2 /= want;
        while(go1 % 2 == 0){
            go1 /= 2;
            lewoW += 1;
        }
        while(go2 % 2 == 0){
            go2 /= 2;
            prawoW += 1;
        }
        if(lewoW > prawoW){
            auto res1 = szukaj(offset + power, twos + 1, true, duze);
            if(res1) return true;
            return szukaj(offset + power + power + power, twos + 1, canFail, duze);
        }
        else{
            auto res1 = szukaj(offset + power + power + power, twos + 1, true, duze);
            if(res1) return true;
            return szukaj(offset + power, twos + 1, canFail, duze);
        }
    }
    else{
        ll param1 = offset + power;
        ll param2 = offset + power + power + power;
        if(los(0, 1) == 0) swap(param1, param2);
        ll go1 = query(param1);
        if(go1 % want != 0) return szukaj(param1, twos + 1, canFail, duze);
        return szukaj(param2, twos + 1, canFail, duze);
    }
}

int dwojki(ll x){
    int ans = 0;
    while(x % 2 == 0){
        x /= 2;
        ans += 1;
    }
    return ans;
}

void solve(){
    cached.clear();
    auto akt = szukaj(-1, 0);
    assert(akt);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int tt = GetT();
    C = GetC();
    rep(te, 1, tt) solve();
    return 0;
}