CF div2 06.08 D 1

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <map>
#define pii pair <int,int>
#define vec vector
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
void cv(vector <int> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}

void cvl(vector <ll> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}


void cvv(vector <vector <int> > &v){
    for (auto x: v) cv(x);
    cout<<"\n";
}

void cvb(vector <bool> v){
    for (bool x: v) cout<<x<<' ';
    cout<<"\n";
}

void cvs(vector <string>  v){
    for (auto a: v){
        cout<<a<<"\n";
    }
}

void cvp(vector <pii> a){
    for (auto p: a){
        cout<<p.first<<' '<<p.second<<"\n";
    }
    cout<<"\n";
}


bool sh=0;

int n, N;

// n = 1 - отдельно

void slv(){
    int N = pow(2, n);
    vector <int> T(2*N - 1);
    for (int i = N - 1; i < 2*N - 1; ++i){
        T[i] = i - (N - 1);
    }
    int lg = n ;
    int to = pow(2, lg);
    int a=0, b;
    int id = pow(2, lg - 2) + 1;
    //cout<<"n N = "<<n<<' '<<N<<"\n";
    if (sh){
        cout<<"T\n";
        cv(T);
        //cout.flush();
    }
    while (lg >= 2){
        int Nnow = pow(2, lg - 2);
        id = 2 * Nnow - 1;
        to = pow(2, lg - 2);
        if (sh){
            cout<<"id = "<<id<<"\n";
            cout<<"lg = "<<lg<<"\n";
            //cout.flush();
        }
        for (int i = 0; i < to; i++){
            a = T[2*id + 1];
            b = T[2*(id+1) + 1];
            cout<<"? "<< (a+1)<<' '<<(b+1)<<"\n";
            cout.flush();
            int r;
            cin>>r;
            if (r == 1){
                if (sh){
                    cout<<"A\n";
                }
                T[id] = a;
                T[id + 1] = T[2*(id+1) + 2];
            }
            else if (r == 2) {
                if (sh){
                    cout<<"B\n";
                }
                T[id + 1] = b;
                T[id] = T[2*id + 2];
            }
            else{//худший случай
                cout<<"? "<< (a+1)<<' '<<(T[2*(id+1) + 2]+1)<<"\n";
                cout.flush();
                cin>>r;
                if (r == 1){
                    if (sh){
                        cout<<"C\n";
                    }
                    T[id] = a;
                    T[id + 1] = b;
                }
                else{//r == 2
                     if (sh){
                        cout<<"D\n";
                    }
                    T[id + 1] = T[2*(id+1) + 2];
                    T[id] = T[2*id + 2];
                }
            }
            id+=2;
            if (sh){
                cout<<"i to = "<<i<<' '<<to<<"\n";
            }
        }
        if (sh){
            cout<<"T\n";
            //cout.flush();
            cv(T);
            //cout.flush();
        }
        lg--;
    }
    a = T[1];
    b = T[2];
    cout<<"? "<< (a+1)<<' '<<(b+1)<<"\n";
    cout.flush();
    int r; cin>>r;
    if (r == 1){
        T[0] = a;
    }
    else{
        T[0] = b;
    }
    cout<<"! "<<(T[0] + 1)<<"\n";
}

int main()
{
    /*ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);*/
    int t=1;
    if (!sh) cin>>t;
    for (int go = 0; go < t; ++go){
        cin>>n;
        slv();
    }
}
/*
1
3
? 1 3
0
? 1 4
1
? 5 7
0
? 5 8
2


? 1 0
*/