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
#include <bits/stdc++.h>
#include "dzilib.h"
using namespace std;

constexpr int NUM = 1e6 + 1e2;
constexpr int DIV = 240;

int div_cnt[NUM + 1];
vector<int> num_list[DIV + 1];

void make() {
    for(int i=1; i<=NUM; i++) {
        for(int j=i; j<=NUM; j+=i) {
            div_cnt[j]++;
        }
    }

    for(int i=1; i<=NUM; i++) {
        num_list[div_cnt[i]].push_back(i);
    }
}

int solve() {
    vector<int> x = num_list[Ask(0)];

    for(int y=1; x.size()>1; y++) {
        vector<int> x_plus_y = num_list[Ask(y)];

        vector<int> common;
        int i = 0, j = 0;

        while(i < x.size() && j < x_plus_y.size()) {
            if(x[i] < x_plus_y[j] - y) {
                i++;
            }
            else if(x[i] == x_plus_y[j] - y) {
                common.push_back(x[i]);
                i++, j++;
            }
            else {
                j++;
            }
        }

        x = common;
    }

    return x[0];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    make();

    int t = GetT();

    while(t--) {
        int x = solve();
        Answer(x);
    }
}