//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops")
//#include <x86intrin.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define PI 3.141592653589793L
#define FAST ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// Use for file I/O;
#define FIN string _fname = "input"; \
			string _is = _fname + ".in", _os = _fname + ".out"; \
			freopen(_is.c_str(), "r", stdin); \
			freopen(_os.c_str(), "w", stdout);

#define FIN2 freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())

using namespace std;
//using namespace __gnu_pbds;
//typedef gp_hash_table<int, int, hash<int>> ht;

const char nl = '\n';

typedef long long ll;
typedef long double ld;
// typedef unsigned int uint;
typedef unsigned long long ull;

const ll inf = 1e9 + 10;
const ll inf2 = 1e18 + 99LL;
const ld inf3 = 1e14;
const ll mod = 998244353;
const ld eps = 1e-9;

const int logn = 20, maxn = 500000, maxm = 1000001, maxn2 = 3;

const bool local = false;

mt19937 rng;

vector<int> tp;
int query(int i, int j, int k) {
    if (local) {
        if (i == j || i == k || j == k) {
            cout << "BAD" << nl;
            return 0;
        }
        int a = abs(tp[i] - tp[j]), b = abs(tp[i] - tp[k]), c = abs(tp[j] - tp[k]);
        return a + b + c - max({a, b, c}) - min({a, b, c});
    } else {
        cout << "? " << i + 1 << ' ' << j + 1 << ' ' << k + 1 << endl;
        int x;
        cin >> x;
        return x;
    }
}

bool aquery(vector<int> p) {
    cout << "! ";
    for (int x: p) cout << x << ' ';
    cout << endl;
    int x;
    cin >> x;
    if (local) {
        cout << "  ";
        for (int i = 0; i < gsize(p); i++) {
            cout << tp[i] << ' ';
        }
        for (int i = 0; i < gsize(p); i++) {
            if (tp[i] != p[i]) {
            cout << "BAD" << endl;
            return false;
            }
        }
        cout << "GOOD" << endl;
        return true;
    }
    return true;
}

int rn(int a, int b) {
    return a + rng() % (b - a + 1);
}

bool solve(int n) {
    tp.assign(n, 0);
    for (int i = 0; i < n; i++) tp[i] = n - i;
    while (tp[0] > tp[1]) shuffle(all(tp), rng);
    
    int i = 0, j = 0, k = 0;
    vector<int> p(n, 0);
    
    while (true) {
        i = rn(0, n - 1);
        do {
            j = rn(0, n - 1);
        } while (i == j);
        do {
            k = rn(0, n - 1);
        } while (i == k || j == k);
    
        if (7*query(i, j, k) < n) {
            break;
        }
    }
   // cout << i << ' ' << j << ' ' << k << ' ' << abs(tp[i] - tp[j]) << ' ' << tp[i] << ' ' << tp[j] << ' ' << tp[k] << endl;
    
    vector<pair<int, int>> res;
    for (int a = 0; a < n; a++) {
        if (a == i || a == j) continue;
        res.emplace_back(query(i, j, a), a);
    }
    sort(allr(res));
    
    int mx = res[0].first;
    vector<int> a1, a2;
    for (auto ttp: res) {
        if (ttp.first == mx) a1.push_back(ttp.second);
        else if (ttp.first == mx - 1) a2.push_back(ttp.second);
        else break;
    }
    
    i = a1[0];
    int tr = 2*n;
    for (int x: a2) {
        int r2 = query(i, x, j);
        if (r2 < tr) {
            tr = r2;
            k = x;
        }
    }
    p[i] = 1;
    p[k] = 2;
    
    
    for (int a = 0; a < n; a++) {
        if (a == i || a == k) continue;
        p[a] = query(i, k, a) + 2;
    }
    
    if (p[0] > p[1]) {
        for (int a = 0; a < n; a++) {
            p[a] = n - p[a] + 1;
        }
    }
    if (!aquery(p)) {
        for (int x: a1) cout << x << ' ' << tp[x] << nl;
        cout << nl;
        for (int x: a2) cout << x << ' ' << tp[x] << nl;
        cout << nl << nl;
        
        
        cout << i << ' ' << k << endl;
        return false;
    }
    return true;
}

int main() {
    FAST;
    rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        solve(n);
    }
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

This is an interactive problem.

There is a secret permutation p (1-indexed) of numbers from 1 to n. More formally, for 1 ≤ i ≤ n, 1 ≤ p[i] ≤ n and for 1 ≤ i < j ≤ n, p[i] ≠ p[j]. It is known that p[1]<p[2].

In 1 query, you give 3 distinct integers a,b,c (1 ≤ a,b,c ≤ n), and receive the median of \{|p[a]-p[b]|,|p[b]-p[c]|,|p[a]-p[c]|\}.

In this case, the median is the 2-nd element (1-indexed) of the sequence when sorted in non-decreasing order. The median of \{4,6,2\} is 4 and the median of \{0,123,33\} is 33.

Can you find the secret permutation in not more than 2n+420 queries?

Note: the grader is not adaptive: the permutation is fixed before any queries are made.

Input

The first line of input contains a single integer t (1 ≤ t ≤ 1000) — the number of testcases.

The first line of each testcase consists of a single integer n (20 ≤ n ≤ 100000) — the length of the secret permutation.

It is guaranteed that the sum of n over all test cases does not exceed 100000.

Interaction

For each testcase, you begin the interaction by reading n.

To perform a query, output "? a b c" where a,b,c is the 3 indices you want to use for the query.

Numbers have to satisfy 1 ≤ a,b,c ≤ n and a ≠ b,b ≠ c,a ≠ c.

For each query, you will receive a single integer x: the median of \{|p[a]-p[b]|,|p[b]-p[c]|,|p[a]-p[c]|\}.

In case your query is invalid or you asked more than 2n+420 queries, the interactor will print "−1" and will finish interaction. You will receive Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts.

When you have determined the secret permutation, output "! p[1] p[2] ... p[n]". If the secret permutation is correct, the interactor will print "1". Otherwise, the interactor will print "-1" and will finish interaction. You will receive Wrong answer verdict. Make sure to exit immediately to avoid getting other verdicts.

After printing a query do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded verdict.

To do this, use:

  * fflush(stdout) or cout.flush() in C++;
  * System.out.flush() in Java;
  * flush(output) in Pascal;
  * stdout.flush() in Python;
  * see documentation for other languages.



Hacks:

To hack, use the following format of test:

The first line should contain a single integer t (1 ≤ t ≤ 1000) — the number of testcases.

The first line of each testcase should contain a single integer n (20 ≤ n ≤ 100000) — the length of the secret permutation.

The following line of should contain n integers p[1],p[2],p[3],…,p[n]. p[1]<p[2] and p must be a permutation of integers from 1 to n.

You must ensure that the sum of n over all testcases does not exceed 100000.

Example

Input


1
20

6

9

1

Output




? 1 5 2

? 20 19 2

! 9 10 19 7 16 18 11 14 15 6 20 8 17 4 5 3 12 2 13 1

Note

The secret permutation is \{9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1\}.

For the first query, the values of (a,b,c) is (1,5,2). Since p[1]=9, p[5]=16 and p[2]=10. The return value is the median of \{|9-16|,|16-10|,|9-10|\} which is 6.

For the second query, the values of (a,b,c) is (20,19,2). Since p[20]=1, p[19]=13 and p[2]=10. The return value is the median of \{|1-13|,|13-10|,|1-10|\} which is 9.

By some miracle, we have figured out that the secret permutation is \{9,10,19,7,16,18,11,14,15,6,20,8,17,4,5,3,12,2,13,1\}. We output it and receive 1 from the interactor, meaning that we have guessed the secret permutation correctly.

### Response

```cpp
//#pragma GCC optimize ("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops")
//#include <x86intrin.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#include <bits/stdc++.h>

#define PI 3.141592653589793L
#define FAST ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// Use for file I/O;
#define FIN string _fname = "input"; \
			string _is = _fname + ".in", _os = _fname + ".out"; \
			freopen(_is.c_str(), "r", stdin); \
			freopen(_os.c_str(), "w", stdout);

#define FIN2 freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);

#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define gsize(x) (int)((x).size())

using namespace std;
//using namespace __gnu_pbds;
//typedef gp_hash_table<int, int, hash<int>> ht;

const char nl = '\n';

typedef long long ll;
typedef long double ld;
// typedef unsigned int uint;
typedef unsigned long long ull;

const ll inf = 1e9 + 10;
const ll inf2 = 1e18 + 99LL;
const ld inf3 = 1e14;
const ll mod = 998244353;
const ld eps = 1e-9;

const int logn = 20, maxn = 500000, maxm = 1000001, maxn2 = 3;

const bool local = false;

mt19937 rng;

vector<int> tp;
int query(int i, int j, int k) {
    if (local) {
        if (i == j || i == k || j == k) {
            cout << "BAD" << nl;
            return 0;
        }
        int a = abs(tp[i] - tp[j]), b = abs(tp[i] - tp[k]), c = abs(tp[j] - tp[k]);
        return a + b + c - max({a, b, c}) - min({a, b, c});
    } else {
        cout << "? " << i + 1 << ' ' << j + 1 << ' ' << k + 1 << endl;
        int x;
        cin >> x;
        return x;
    }
}

bool aquery(vector<int> p) {
    cout << "! ";
    for (int x: p) cout << x << ' ';
    cout << endl;
    int x;
    cin >> x;
    if (local) {
        cout << "  ";
        for (int i = 0; i < gsize(p); i++) {
            cout << tp[i] << ' ';
        }
        for (int i = 0; i < gsize(p); i++) {
            if (tp[i] != p[i]) {
            cout << "BAD" << endl;
            return false;
            }
        }
        cout << "GOOD" << endl;
        return true;
    }
    return true;
}

int rn(int a, int b) {
    return a + rng() % (b - a + 1);
}

bool solve(int n) {
    tp.assign(n, 0);
    for (int i = 0; i < n; i++) tp[i] = n - i;
    while (tp[0] > tp[1]) shuffle(all(tp), rng);
    
    int i = 0, j = 0, k = 0;
    vector<int> p(n, 0);
    
    while (true) {
        i = rn(0, n - 1);
        do {
            j = rn(0, n - 1);
        } while (i == j);
        do {
            k = rn(0, n - 1);
        } while (i == k || j == k);
    
        if (7*query(i, j, k) < n) {
            break;
        }
    }
   // cout << i << ' ' << j << ' ' << k << ' ' << abs(tp[i] - tp[j]) << ' ' << tp[i] << ' ' << tp[j] << ' ' << tp[k] << endl;
    
    vector<pair<int, int>> res;
    for (int a = 0; a < n; a++) {
        if (a == i || a == j) continue;
        res.emplace_back(query(i, j, a), a);
    }
    sort(allr(res));
    
    int mx = res[0].first;
    vector<int> a1, a2;
    for (auto ttp: res) {
        if (ttp.first == mx) a1.push_back(ttp.second);
        else if (ttp.first == mx - 1) a2.push_back(ttp.second);
        else break;
    }
    
    i = a1[0];
    int tr = 2*n;
    for (int x: a2) {
        int r2 = query(i, x, j);
        if (r2 < tr) {
            tr = r2;
            k = x;
        }
    }
    p[i] = 1;
    p[k] = 2;
    
    
    for (int a = 0; a < n; a++) {
        if (a == i || a == k) continue;
        p[a] = query(i, k, a) + 2;
    }
    
    if (p[0] > p[1]) {
        for (int a = 0; a < n; a++) {
            p[a] = n - p[a] + 1;
        }
    }
    if (!aquery(p)) {
        for (int x: a1) cout << x << ' ' << tp[x] << nl;
        cout << nl;
        for (int x: a2) cout << x << ' ' << tp[x] << nl;
        cout << nl << nl;
        
        
        cout << i << ' ' << k << endl;
        return false;
    }
    return true;
}

int main() {
    FAST;
    rng = mt19937(chrono::steady_clock::now().time_since_epoch().count());
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        solve(n);
    }
}

```