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
116
117
118
119
120
121
122
123
// Przykładowe niepoprawne rozwiązanie do zadania Dzielniki.
#include <bits/stdc++.h>
#include "dzilib.h"

using namespace std;

#define eb emplace_back
#define MOD 1000000007

using ll = long long;

#define ita(i,s,e) for(long long int i=s;i<=e;i++)
#define urs(r...)typename decay<decltype(r)>::type
#define rep(i,n)for(urs(n)i=0;i<(n);++i)


ll t, n, q, c;
int hash_window = 50;
unordered_map<int, vector<int>> hash_reverse;

ll powmod(ll a, ll x) {
    ll res = 1;
    ll exp = a;
    while (x) {
        if (x&1) {
            res = (res*exp) % MOD;
        }
        exp = (exp*exp) % MOD;
        x = x >> 1;
    }
    return res;
}

int divisors(ll n) {
    long long divisors = 0;
	long long i = 1;
	for (; i*i < n; i++)
		if (n % i == 0)
			divisors+=2;
	if (i*i == n) divisors++;
	return divisors;
}

ll phash(deque<int> v) {
    ll ret = 0;
    for (int i : v)
    {
        ret = ret*257 + i;
        ret %= MOD;
    }
    return ret;
}


void precompute_hash() {
    deque<int> q;
    ita(i, 1, hash_window) {
        q.push_back(divisors(i));
    }

    ll h = phash(q);
    hash_reverse[h].eb(1);


    ita(i, 2, n) {
        int last = divisors(i+hash_window-1);
        q.pop_front();
        q.push_back(last);
        hash_reverse[phash(q)].eb(i);
    }
}


void solve() {
    deque<int> q;
    rep(i, hash_window) {
        q.push_back(Ask(i));
    }
    ll h = phash(q);

    vector<int> candidates = hash_reverse[h];

    int further = 100;
    while (candidates.size() > 1) {
        int div0 = divisors(candidates[0]+further);
        int div1 = divisors(candidates[1]+further);

        if (div0 != div1) {
            int div = Ask(further);
            
            vector<int> remaining;
            for (int c: candidates) {
                if (divisors(c+further) == div) {
                    remaining.eb(c);
                }
            }
            swap(candidates, remaining);
        }
        further++;
    }

    Answer(candidates[0]);
}


int main() {
  t = GetT();
  q = GetQ();
  c = GetC();
  n = GetN();
  if (n > 1e6) {
    while(t--) {
    Answer(1);
  }
    return 0;
  };
  precompute_hash();
  while(t--) {
    solve();
  }
    
  return 0;
}