#include <iostream>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <string>

using namespace std;

const int maxn = 5982;
const int maxl = 5000;
const int bb = 10000;
const int max_at_dep[] = {1601,2017,2608,4427,1481,1487,1355,11,24,10};
const int min_at_dep[] = {1601,181,152,28,22,6,6,1,2,0};

int f[maxn+1][maxl];
int len[maxn+1];

inline int get(int i,int k){
    int x = f[i][k / 4];
    switch(k % 4){
        case 0:
          return x % 10;
        case 1:
          return (x / 10) % 10;
        case 2:
          return (x / 100) % 10;
        case 3:
          return (x / 1000) % 10;
        default:
          return x % 10;
    }
}

int ct[10];
int maxdep = 0;

struct node{
    node* ch[10];
    int index;
    bool is_leaf;
};

node* decision_tree;

node* dfs(int dep,vector<int> candidates){
  int n = candidates.size();
    if (candidates.size() <= 1){
      maxdep = max(maxdep, dep);
      node* tree = new node;
      for (int i = 0;i < 10;i++){
          tree->ch[i] = NULL;
      }
      tree->index = (n == 1) ? candidates[0] : -1;
      tree->is_leaf = true;
      return tree;
    }
    // find opt divide
    int opt_divide = n;
    int id = 0;
    for (int i = min_at_dep[dep];i <= min(max_at_dep[dep],len[candidates[n-1]] * 4-1);i++){
        int index = 0;
        memset(ct,0,sizeof ct);
        bool tf = true;
        for (auto c : candidates){
            ct[get(c,i)]++;
            if (ct[get(c,i)] > opt_divide){
              tf = false;
              break;
            }
        }
        if (!tf) continue;
        for (int j = 0;j < 10;j++){
            index = max(index, ct[j]);
        }
        if (index < opt_divide){
            opt_divide = index;
            id = i;
        }
    }
    node* ret = new node;
    ret->is_leaf = false;
    ret->index = id;
    for (int i = 0;i < 10;i++){
        vector<int> a;
        for (auto c : candidates){
            if (get(c,id) == i){
                a.push_back(c);
            }
        }
        ret->ch[i] = dfs(dep+1,a);
    }
    return ret;
}

int main(){
    f[0][0] = 1;
    len[0] = 1;
    for (int i = 1;i <= maxn;i++){
        for (int j = 0;j < len[i-1];j++){
            f[i][j] += f[i-1][j] * i;
            f[i][j+1] += f[i][j] / bb;
            f[i][j] %= bb;
        }
        len[i] = len[i-1];
        while (f[i][len[i]] > 0){
          f[i][len[i]+1] += f[i][len[i]] / bb;
          f[i][len[i]] %= bb;
          len[i]++;
        }
    }

    vector<int> init;
    for (int i = 1;i <= maxn;i++){
        init.push_back(i);
    }
    decision_tree = dfs(0, init);

    int t;
    cin >> t;
    while (t--){
        node* cur = decision_tree;
        while (!(cur->is_leaf)){
            cout << "?" << " " << cur->index << endl;
            int t;
            cin >> t;
            cur = cur->ch[t];
        }
        cout << "!" << " " << cur->index << endl;
        string ret;
        cin >> ret;
        if (ret == "NO"){
            assert(false);
            return 0;
        }
    }
  }

answer.code: In function ‘int main()’:
answer.code:132:13: error: ‘assert’ was not declared in this scope
  132 |             assert(false);
      |             ^~~~~~
answer.code:5:1: note: ‘assert’ is defined in header ‘<cassert>’; did you forget to ‘#include <cassert>’?
    4 | #include <cstdlib>
  +++ |+#include <cassert>
    5 | #include <string>