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
114
115
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...)
#endif

#define x first
#define y second
#define ir(a, x, b) ((a) <= (x) && (x) <= (b))
#define vec vector
#define rep(i, a, b) for (ll i = a; i < (b); ++i)
#define all(x) (x).begin(), (x).end()

#include "dzilib.h"

using ll = long long;

long long numberOfDivisors(long long num) {
    long long total = 1;
    for (int i = 2; (long long)i * i <= num; i++) {
        if (num % i == 0) {
            int e = 0;
            do {
                e++;
                num /= i;
            } while (num % i == 0);
            total *= e + 1;
        }
    }
    if (num > 1) {
        total *= 2;
    }
    return total;
}

mt19937_64 gen;

ll add;
map<ll, int> mm;
ll ask(ll x) {
    if (!mm.contains(x)) mm[x] = Ask(x+add);
    // asks.push_back({power, {x, mm[x]}});
    return mm[x];
}

const int K = 30;
bool verify(ll C) {
    if (C < 0) return false;
    for (auto [a, b] : mm) {
        // ask(a) = div(C+a) = mm[a] = b
        ll twos = 0, x = C+a;
        while (x % 2 == 0) {
            x /= 2;
            twos++;
        }
        if (x < ll(1e9)) {
            if (b % (twos+1) != 0) return false;
            if (b != numberOfDivisors(x)*(twos+1)) return false;
        }
    }
    return true;
}

void solve() {
    ll c = GetC();
    ll n = GetN();
    add = gen() % 100000;
    mm.clear();
    
    int base = 0;
    while (true) {
        debug("here", base);
        if (ask(base) % 5 == 0 && ask(base+32) % 5 == 0 && ask(base+64) % 5 == 0) {
            break;       
        }
        base++;
    }
    
    debug(base);
    ll val = 16;
    rep (power, 4, K) { // invariant: 2^power | C+base
        // debug(power, val);
        // assert((1000+add+base) % (1ll << power) == 0);
        rep (k, 0, 1000) {
            if (ask(base + k*val) % (power+1) != 0) {
                // 2^(power+1) | base + k*val
                base = base + (k%2)*val;
                break;
            }
        }
        val *= 2;
    }
    int x = 1;
    debug(add, base);
    while (true) {
        ll y = (1ll << K)*x-base;
        debug("here", x, y);
        if (verify(y)) {
            Answer(y-add); // TODO
            return;
        }
        x++;
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = GetT();
    while (t--) solve();
    return 0;
}