#include <algorithm>
#include <csignal>
#include <cstdarg>
#include <cstdio>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <random>
#include <set>
#include <queue>
#include <vector>
using namespace std;

const int T_LIMIT = 10;
const int N_LIMIT = 2000;
const int QUESTION_LIMIT = 10000;

int SUBTASK;

string _judge_msg = "";

[[noreturn]] void grade(double score, const string& msg) {
    cout << fixed << setprecision(10) << score << endl;
    cerr << msg << endl;
    if(!_judge_msg.empty()) cerr << "ADMIN_MESSAGE: " << _judge_msg << endl;
    exit(0);
}
void judge_message(const string& msg) {
    if(!_judge_msg.empty()) _judge_msg += "; ";
    _judge_msg += msg;
}
[[noreturn]] void wrong_answer(const string& msg) { judge_message(msg); grade(0, "translate:wrong"); }
[[noreturn]] void accept(double score) { judge_message("score: " + to_string(score)); grade(score, score==1.0 ? "translate:success" : "translate:partial"); }
[[noreturn]] void judge_error(const string& msg) { judge_message(msg); cerr << "ADMIN_MESSAGE: " << _judge_msg << endl; exit(1); }
void myassert(bool condition, const string& msg) { if (!condition) wrong_answer(msg); }
double score(int max_N, double x_s) { 
    double sc;
    x_s = max( 1., x_s );
    if (SUBTASK == 3) {
        double max_score = 15;
        sc = min( max_score, 3. + 19./pow(x_s,1.5) );
        sc = round(sc) / max_score;
    }
    if (SUBTASK == 4) {
        double max_score = 65;
        sc = min( max_score, 3. + 91./pow(x_s,1.5) );
        sc = round(sc) / max_score;
    }
    return sc;
}

FILE* fifo_in; // read from contestant
FILE* fifo_out; // write to contestant
mt19937 rng;

void write_message(const char* format, ...) {
    va_list args;
    va_start(args, format);
    int res;
    res = vfprintf(fifo_out, format, args);
    myassert(res > 0, "Pipe to contestant closed unexpectedly."); // here res==0 is also bad, we need to actually write some bytes
    res = fflush(fifo_out);
    myassert(res != EOF, "Pipe to contestant closed unexpectedly.");
}

char read_char() {
    char ans;
    int res = fscanf(fifo_in, " %c", &ans);
    myassert(res != EOF, "Contestant's output ended prematurely.");
    return ans;
}

int read_int() {
    int ans;
    int res = fscanf(fifo_in, " %d", &ans);
    myassert(res != EOF, "Contestant's output ended prematurely.");
    myassert(res == 1, "Contestant's output contained something else when int was expected.");
    return ans;
}

int read_testcase_int(int lo, int hi, string name="") {
    int ans;
    cin >> ans;
    if (!cin) judge_error("Wrong input format.");
    // cerr << name << " := " << ans << endl;
    if (!(lo <= ans && ans <= hi)) judge_error("Out-of-range value (" + name + ") in input file.");
    return ans;
}

string read_testcase_token() {
    string ans;
    cin >> ans;
    if (!cin) judge_error("Wrong input format.");
    return ans;
}

vector<int> reversed(const vector<int> &perm) { vector<int> rperm = perm; reverse( rperm.begin(), rperm.end() ); return rperm; }
vector<int> normalize(const vector<int> &perm) { return min( perm, reversed(perm) ); }
vector<int> invert(const vector<int> &perm) { int N = perm.size(); vector<int> ans(N, -1); for (int n=0; n<N; ++n) ans[perm[n]]=n; return ans; }

void play_deterministic(int N, const vector<int>& G, int& max_questions_asked, double& max_questions_ratio) {
    vector<int> S = invert(G);
    for (int n=0; n<N; ++n) if (S[n] == -1) judge_error("Duplicate value in G in input file.");

    write_message("%d\n", N);

    int questions_asked = 0;
    while (true) {
        char cmd = read_char();
        myassert(cmd == '?' || cmd == '!', "Invalid command, must be ? or !.");
        if (cmd == '?') {
            ++questions_asked;
            myassert(questions_asked <= QUESTION_LIMIT, "Too many questions asked.");
            int x = read_int();
            int y = read_int();
            int z = read_int();
            myassert(0 <= x && x < N, "Value of x out of range.");
            myassert(0 <= y && y < N, "Value of y out of range.");
            myassert(0 <= z && z < N, "Value of z out of range.");
            myassert(x != y && x != z && y != z, "Values of x, y, z not distinct.");
            int ans = max({S[x], S[y], S[z]}) - min({S[x], S[y], S[z]}) + 1;
            write_message("%d\n", ans);
        }
        if (cmd == '!') {
            vector<int> theirG(N);
            for (int n=0; n<N; ++n) theirG[n] = read_int();
            myassert(theirG == G || theirG == reversed(G), "Reported answer is not the correct permutation.");
            break;
        }
    }
    max_questions_asked = max(max_questions_asked, questions_asked);
    max_questions_ratio = max(max_questions_ratio, 1. * questions_asked / N);
}

void play_fixed_seq(int N, const vector<int>& position_assignment, int& max_questions_asked, double& max_questions_ratio) {
    map<int, int> seen;
    queue<int> next_value;
    for (int x : position_assignment) next_value.push(x);

    write_message("%d\n", N);

    int questions_asked = 0;
    while (true) {
        char cmd = read_char();
        myassert(cmd == '?' || cmd == '!', "Invalid command, must be ? or !.");
        if (cmd == '?') {
            ++questions_asked;
            myassert(questions_asked <= QUESTION_LIMIT, "Too many questions asked.");
            int x = read_int();
            int y = read_int();
            int z = read_int();
            myassert(0 <= x && x < N, "Value of x out of range.");
            myassert(0 <= y && y < N, "Value of y out of range.");
            myassert(0 <= z && z < N, "Value of z out of range.");
            myassert(x != y && x != z && y != z, "Values of x, y, z not distinct.");
            if (rng()&1) swap(x,y);
            if (rng()&1) swap(x,z);
            if (rng()&1) swap(y,z);
            if (!seen.count(x)) { seen[x] = next_value.front(); next_value.pop(); }
            if (!seen.count(y)) { seen[y] = next_value.front(); next_value.pop(); }
            if (!seen.count(z)) { seen[z] = next_value.front(); next_value.pop(); }
            int ans = max({seen[x], seen[y], seen[z]}) - min({seen[x], seen[y], seen[z]}) + 1;
            write_message("%d\n", ans);
        }
        if (cmd == '!') {
            vector<int> theirG(N);
            for (int n=0; n<N; ++n) theirG[n] = read_int();

            if (next_value.size() > 1u) myassert(false, "Reported answer when multiple ones were still possible.");
            for (int n=0; n<N; ++n) if (!seen.count(n)) { seen[n] = next_value.front(); next_value.pop(); }
            vector<int> S(N);
            for (int n=0; n<N; ++n) S[n] = seen[n];
            vector<int> G = invert(S);

            myassert(theirG == G || theirG == reversed(G), "Reported answer is not the correct permutation.");
            break;
        }
    }
    max_questions_asked = max(max_questions_asked, questions_asked);
    max_questions_ratio = max(max_questions_ratio, 1. * questions_asked / N);
}

int place_smart_helper(int g, vector<int> &S, vector<int> &G) {
    if (S[g] != -1) return S[g];
    int N = S.size();
    for (int x=N/2-10; x<=N/2+10; ++x) {
        if (x >= 0 && x < N && G[x] == -1) return x;
    }
    for (int i=0; i<10; ++i) {
        int x = N/4 + rng()%(N/2);
        bool good = true;
        if (G[x] != -1) good = false;
        if (x > 0 && G[x-1] != -1) good = false;
        if (x+1 < N && G[x+1] != -1) good = false;
        if (good) return x;
    }
    for (int i=0; i<10; ++i) {
        int x = N/4 + rng()%(N/2);
        bool good = true;
        if (G[x] != -1) good = false;
        if (good) return x;
    }
    while (true) {
        int x = rng()%N;
        if (G[x] == -1) return x;
    }
}

int place_smart(int g, vector<int> &S, vector<int> &G) {
    int s = place_smart_helper(g, S, G);
    S[g] = s;
    G[s] = g;
    return s;
}

void play_ambiguous(int N, int& max_questions_asked, double& max_questions_ratio, bool prefer_shortest=true, bool avoid_inside=false, bool prioritize_pairs=true) {
    write_message("%d\n", N);

    vector<int> S(N, -1), G(N, -1);
    map< pair<int,int>, vector<int> > open_pairs;

    int questions_asked = 0;
    while (true) {
        char cmd = read_char();
        myassert(cmd == '?' || cmd == '!', "Invalid command, must be ? or !.");
        if (cmd == '?') {
            ++questions_asked;
            myassert(questions_asked <= QUESTION_LIMIT, "Too many questions asked.");
            int x = read_int();
            int y = read_int();
            int z = read_int();
            myassert(0 <= x && x < N, "Value of x out of range.");
            myassert(0 <= y && y < N, "Value of y out of range.");
            myassert(0 <= z && z < N, "Value of z out of range.");
            myassert(x != y && x != z && y != z, "Values of x, y, z not distinct.");

            int placed = 0;
            if (S[x] != -1) ++placed;
            if (S[y] != -1) ++placed;
            if (S[z] != -1) ++placed;

            if (placed == 3) {
                int ans = max({S[x], S[y], S[z]}) - min({S[x], S[y], S[z]}) + 1;
                write_message("%d\n", ans);
            }

            if (placed <= 1) {
                place_smart(x, S, G);
                place_smart(y, S, G);
                place_smart(z, S, G);
                int ans = max({S[x], S[y], S[z]}) - min({S[x], S[y], S[z]}) + 1;
                write_message("%d\n", ans);
            }
            
            if (placed == 2) {
                if (S[x] == -1) swap(x, z);
                if (S[y] == -1) swap(y, z);
                if (x > y) swap(x, y);

                if (prioritize_pairs) {
                    bool done = false;
                    while (!open_pairs[{x, y}].empty()) {
                        int oz = open_pairs[{x, y}].back();
                        open_pairs[{x, y}].pop_back();
                        int fz = -1;
                        for (int sz=0; sz<N; ++sz) if (G[sz] == -1) {
                            int ans = max({S[x], S[y], sz}) - min({S[x], S[y], sz}) + 1;
                            if (ans == max({S[x], S[y], S[oz]}) - min({S[x], S[y], S[oz]}) + 1) {
                                fz = sz; break;
                            }
                        }
                        if (fz == -1) continue;
                        S[z] = fz;
                        G[fz] = z;
                        int ans = max({S[x], S[y], S[z]}) - min({S[x], S[y], S[z]}) + 1;
                        write_message("%d\n", ans);
                        done = true;
                        break;
                    }
                    if (done) continue;   
                }

                vector<int> dist(N+1, 0);
                for (int sz=0; sz<N; ++sz) if (G[sz] == -1) {
                    int ans = max({S[x], S[y], sz}) - min({S[x], S[y], sz}) + 1;
                    dist[ans] += 1;
                }
                int xydist = max({S[x], S[y]}) - min({S[x], S[y]}) + 1;
                if (avoid_inside) {
                    for (int i=0; i<=N; ++i) if (dist[i] > 0 && i != xydist) dist[i] += 1000;
                }
                int maxd = *max_element( dist.begin(), dist.end() );
                vector<int> cands;
                for (int i=0; i<=N; ++i) if (dist[i] == maxd) cands.push_back(i);
                int ans;
                if (prefer_shortest) {
                    ans = cands[0];
                } else {
                    ans = cands[ rng() % cands.size() ];
                }
                write_message("%d\n", ans);
                vector<int> pcands;
                for (int sz=0; sz<N; ++sz) if (G[sz] == -1) {
                    int cd = max({S[x], S[y], sz}) - min({S[x], S[y], sz}) + 1;
                    if (cd == ans) pcands.push_back(sz);
                }
                int sz = pcands[ rng() % pcands.size() ];
                S[z] = sz;
                G[sz] = z;
                if (ans > xydist) open_pairs[{x,y}].push_back(z);
            }
        }
        if (cmd == '!') {
            vector<int> theirG(N);
            for (int n=0; n<N; ++n) theirG[n] = read_int();

            int minuses = 0;
            for (int s : S) if (s == -1) ++minuses;
            if (minuses > 1) myassert(false, "Reported answer when multiple ones were still possible.");

            if (minuses == 1) {
                int i=0; while (S[i] != -1) ++i;
                int j=0; while (G[j] != -1) ++j;
                S[i] = j;
                G[j] = i;
            }

            myassert(theirG == G || theirG == reversed(G), "Reported answer is not the correct permutation.");
            break;
        }
    }
    max_questions_asked = max(max_questions_asked, questions_asked);
    max_questions_ratio = max(max_questions_ratio, 1. * questions_asked / N);
}

void play_merge_segments(int N, int& max_questions_asked, double& max_questions_ratio, bool small_into_big=true) {
    vector<int> color(N);
    iota(color.begin(), color.end(), 0);

    vector< vector<int> > G(N);
    for (int n=0; n<N; ++n) G[n] = {n};
    vector< map<int,int> > S(N);
    for (int n=0; n<N; ++n) S[n][n] = 0;

    write_message("%d\n", N);

    int questions_asked = 0;
    while (true) {
        char cmd = read_char();
        myassert(cmd == '?' || cmd == '!', "Invalid command, must be ? or !.");
        if (cmd == '?') {
            ++questions_asked;
            myassert(questions_asked <= QUESTION_LIMIT, "Too many questions asked.");
            int x = read_int();
            int y = read_int();
            int z = read_int();
            myassert(0 <= x && x < N, "Value of x out of range.");
            myassert(0 <= y && y < N, "Value of y out of range.");
            myassert(0 <= z && z < N, "Value of z out of range.");
            myassert(x != y && x != z && y != z, "Values of x, y, z not distinct.");
            set<int> scolors;
            scolors.insert(color[x]); scolors.insert(color[y]); scolors.insert(color[z]);
            vector<int> vcolors(scolors.begin(), scolors.end());
            int cc = vcolors[0];
            for (unsigned i=1; i<vcolors.size(); ++i) { 
                int nc = vcolors[i];
                if (small_into_big) {
                    if (G[color[cc]].size() < G[color[nc]].size()) swap(cc, nc);
                } else {
                    if (rng()&1) swap(cc, nc);
                }
                if (rng()&1) reverse(G[nc].begin(), G[nc].end());
                int sz = G[cc].size();
                for (int x : G[nc]) { color[x]=cc; G[cc].push_back(x); S[cc][x] = sz; ++sz; }
            }
            int ans = max({S[cc][x], S[cc][y], S[cc][z]}) - min({S[cc][x], S[cc][y], S[cc][z]}) + 1;
            write_message("%d\n", ans);
        }
        if (cmd == '!') {
            vector<int> theirG(N);
            for (int n=0; n<N; ++n) theirG[n] = read_int();

            myassert( *min_element(color.begin(), color.end()) == *max_element(color.begin(), color.end()),
                "Reported answer when multiple ones were still possible.");

            myassert(theirG == G[color[0]] || theirG == reversed(G[color[0]]), "Reported answer is not the correct permutation.");
            break;
        }
    }
    max_questions_asked = max(max_questions_asked, questions_asked);
    max_questions_ratio = max(max_questions_ratio, 1. * questions_asked / N);
}

void check_and_play_sample() {
    vector<int> all_input;
    int x;
    while (cin >> x) all_input.push_back(x);
    if (all_input != vector<int>{5, 4, 2, 0, 1, 3}) judge_error("No fingerprint but not the sample input.");
    write_message("%d\n", 1); // number_of_testcases
    int N = 5;
    vector<int> G = {4, 2, 0, 1, 3};
    int max_questions_asked = 0;
    double max_questions_ratio = 0;
    play_deterministic(N, G, max_questions_asked, max_questions_ratio);
    judge_message("max queries: " + to_string(max_questions_asked));
    accept(1.);
}

vector<int> get_seq_middle(int N) {
    vector<int> answer(1, N/2);
    int start = N/2;
    for (int step=1; step<=N+7; ++step) {
        int x = start+step, y = start-step;
        if (rng()&1) swap(x,y);
        if (0 <= x && x < N) answer.push_back(x);
        if (0 <= y && y < N) answer.push_back(y);
    }
    return answer;
}

vector<int> get_seq_bimodal(int N) {
    vector< pair<int,int> > options;
    for (int n=0; n<N; ++n) options.push_back( { min( abs(n-N/4), abs(n-3*N/4) ), n } );
    sort( options.begin(), options.end() );
    vector<int> answer;
    for (auto rec:options) answer.push_back(rec.second); 
    return answer;
}

vector<int> get_seq_bimodal2(int N) {
    vector< pair<int,int> > options;
    for (int n=0; n<N; ++n) {
        int a = abs(n-N/4);
        int b = abs(n-3*N/4);
        if (a < N/4) options.push_back({a,n}); else options.push_back({N+b,n});
    }
    sort( options.begin(), options.end() );
    vector<int> answer;
    for (auto rec:options) answer.push_back(rec.second); 
    return answer;
}

vector<int> get_seq_midbimodal(int N) {
    vector< pair<int,int> > options;
    for (int n=0; n<N; ++n) {
        int a = abs(n-N/4);
        int b = abs(n-2*N/4);
        int c = abs(n-3*N/4);
        if (b < N/4) options.push_back({b,n}); else options.push_back({N+min(a,c),n});
    }
    sort( options.begin(), options.end() );
    vector<int> answer;
    for (auto rec:options) answer.push_back(rec.second); 
    return answer;
}

vector<int> get_seq_midbimodal2(int N) {
    vector< pair<int,int> > options;
    for (int n=0; n<N; ++n) {
        int a = abs(n-N/4);
        int b = abs(n-2*N/4);
        int c = abs(n-3*N/4);
        if (b < N/4) { options.push_back({b,n}); continue; }
        if (a < c) options.push_back({N+a,n}); else options.push_back({2*N+c,n});
    }
    sort( options.begin(), options.end() );
    vector<int> answer;
    for (auto rec:options) answer.push_back(rec.second); 
    return answer;
}

vector<int> get_seq_middle_fuzzy(int N) {
    vector<bool> used(N, false);
    vector<int> answer;
    for (int step=0; step<N; ++step) {
        while (true) {
            int val = rng() % (2*step+1);
            int x = N/2 + val - step;
            if (0 <= x && x < N && !used[x]) { answer.push_back(x); used[x]=true; break; }
        }
    }
    return answer;
}

vector<int> get_seq_sides(int N) {
    vector<int> answer = get_seq_middle(N);
    reverse(answer.begin(), answer.end());
    return answer;
}

vector<int> get_seq_sides_fuzzy(int N) {
    vector<int> answer = get_seq_middle_fuzzy(N);
    reverse(answer.begin(), answer.end());
    return answer;
}

vector<int> get_seq_step(int N, int mod) {
    vector<int> good, bad;
    for (int n=0; n<N; ++n) { if (n%mod) bad.push_back(n); else good.push_back(n); }
    shuffle(good.begin(), good.end(), rng);
    shuffle(bad.begin(), bad.end(), rng);
    for (int x:bad) good.push_back(x);
    return good;
}

vector<int> get_seq_step_byclass(int N, int mod) {
    vector< vector<int> > classes(mod);
    for (int n=0; n<N; ++n) classes[n%mod].push_back(n);
    for (int m=0; m<mod; ++m) shuffle(classes[m].begin(), classes[m].end(), rng);
    shuffle(classes.begin(), classes.end(), rng);
    vector<int> answer;
    for (auto &row : classes) for (auto &x : row) answer.push_back(x);
    return answer;
}

vector<int> get_sparse(int N, int mindist) {
    set<int> savailable;
    for (int n=0; n<N; ++n) savailable.insert(n);
    vector<bool> vavailable(N, true);
    vector<int> answer;
    while (!savailable.empty()) {
        int x;
        while (true) {
            x = rng()%N;
            if (vavailable[x]) break;
        }
        answer.push_back(x);
        for (int y=x-mindist+1; y<=x+mindist-1; ++y) {
            if (y < 0 || y >= N) continue;
            savailable.erase(y);
            vavailable[y] = false;
        }
    }
    for (int n=0; n<N; ++n) vavailable[n] = true;
    for (int x : answer) vavailable[x] = false;
    vector<int> remaining;
    for (int n=0; n<N; ++n) if (vavailable[n]) remaining.push_back(n);
    shuffle(remaining.begin(), remaining.end(), rng);
    for (int x : remaining) answer.push_back(x);
    return answer;
}

/*
DISTORTS = [ distort_local_swaps, distort_arbitrary_swaps, distort_reverse, distort_arbitrary_moves,
    distort_rotate, distort_reverse_segment, distort_move_segment ]
*/

int main(int argc, char **argv) {
    signal(SIGPIPE, SIG_IGN);
    // important: open the pipes in the opposite order from what's done on the other end
    fifo_out = fopen(argv[2], "w");
    fifo_in = fopen(argv[1], "r");
    if (!fifo_in || !fifo_out) judge_error("Could not open pipes.");

    rng.seed( 47000001 );

    int fingerprint = read_testcase_int(-47, 1, "fingerprint");
    // dumb workaround to handle sample input
    if (fingerprint != -47 && fingerprint != 1) judge_error("Out-of-range value (fingerprint) in input file.");
    if (fingerprint == 1) check_and_play_sample(); 
    SUBTASK = read_testcase_int(1, 4, "subtask");

    int number_of_testcases = read_testcase_int(1, T_LIMIT, "number_of_testcases");
    write_message("%d\n", number_of_testcases);

    int max_questions_asked = 0;
    double max_questions_ratio = 0;
    int max_N = 0;

    for (int test=1; test<=number_of_testcases; ++test) {
        int N = read_testcase_int(5, N_LIMIT, "N");
        max_N = max( max_N, N );

        int deterministic = read_testcase_int(0, 2, "deterministic");
        // judge_message("N = " + to_string(N) + " deterministic = " + to_string(deterministic));

        string strategy;
        vector<int> seq, G;
        switch (deterministic) {
            case 0:
                strategy = read_testcase_token();
                if (strategy == "merge_segments") { play_merge_segments(N, max_questions_asked, max_questions_ratio); continue; }
                if (strategy == "merge_segments2") { play_merge_segments(N, max_questions_asked, max_questions_ratio, false); continue; }
                if (strategy >= "ambiguous000" && strategy <= "ambiguous111") {
                    bool p1 = (strategy.size() >= 10 && strategy[9] == '1');
                    bool p2 = (strategy.size() >= 11 && strategy[10] == '1');
                    bool p3 = (strategy.size() >= 12 && strategy[11] == '1');
                    play_ambiguous(N, max_questions_asked, max_questions_ratio, p1, p2, p3);
                    continue;
                }
                if (strategy == "middle") seq = get_seq_middle(N);
                if (strategy == "middle_fuzzy") seq = get_seq_middle_fuzzy(N);
                if (strategy == "sides") seq = get_seq_sides(N);
                if (strategy == "sides_fuzzy") seq = get_seq_sides_fuzzy(N);
                if (strategy == "even") seq = get_seq_step(N, 2);
                if (strategy == "mul3") seq = get_seq_step(N, 3);
                if (strategy == "mul3_byclass") seq = get_seq_step_byclass(N, 3);
                if (strategy == "sqrt") seq = get_seq_step(N, int(sqrt(N)));
                if (strategy == "sqrt_byclass") seq = get_seq_step_byclass(N, int(sqrt(N)));
                if (strategy == "mul10_fuzzy") seq = get_sparse(N, 10);
                if (strategy == "sqrt_fuzzy") seq = get_sparse(N, max(2, int(sqrt(N))-2));
                if (strategy == "bimodal") seq = get_seq_bimodal(N);
                if (strategy == "bimodal2") seq = get_seq_bimodal2(N);
                if (strategy == "midbimodal") seq = get_seq_midbimodal(N);
                if (strategy == "midbimodal2") seq = get_seq_midbimodal2(N);
                if (seq.empty()) judge_error("Unknown strategy.");
                play_fixed_seq(N, seq, max_questions_asked, max_questions_ratio);
                break;
            case 1:
                G.resize(N);
                for (int n=0; n<N; ++n) G[n] = read_testcase_int(0, N-1, "G[i]");
                play_deterministic(N, G, max_questions_asked, max_questions_ratio);
                break;
            case 2:
                seq.resize(N);
                for (int n=0; n<N; ++n) seq[n] = read_testcase_int(0, N-1, "seq[i]");
                play_fixed_seq(N, seq, max_questions_asked, max_questions_ratio);
                break;
        }
    }

    judge_message("max queries: " + to_string(max_questions_asked));
    if (SUBTASK == 1 || SUBTASK == 2) accept(1.);
    accept(score(max_N, max_questions_ratio));
}


