#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
ll MOD;
const ll root = 3;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 100001;
int res[mxN];
int ord[mxN];
int val[mxN];
int cnt[mxN];
int p[mxN];
int n;
int len;
int query(int a, int b, int c) {
    cout<<"? "<<a<<" "<<b<<" "<<c<<endl;
    int x;
    cin>>x;
    return x;
    /*vector<int> ok = {abs(p[a]-p[b]), abs(p[b]-p[c]), abs(p[a]-p[c])};
    sort(ok.begin(), ok.end());
    return ok[1];*/
}
void osolve() {
    vector<int> guys;
    ord[2] = ord[1] + len;
    owo(i, 3, n+1) {
        if(val[i]==len || (val[i]==len+1 && val[i]==2))guys.senpai(i);
    }
    ttgl anchor = {-1, -1};
    ttgl anchor2 = {-1, -1};
    owo(i, 0, guys.size()) {
        owo(j, 0, guys.size()) {
            if(i^j) {
                if(query(1, guys[i], guys[j])==1)anchor = {guys[i], guys[j]};
                if(query(2, guys[i], guys[j])==1)anchor2 = {guys[i], guys[j]};
            }
        }
    }
    if(anchor.first!=-1) {
        if(len==1) {
            if(query(anchor.first, 1, 2)!=1) {
                swap(anchor.first, anchor.second);
            }
        }
        owo(i, 3, n+1) {
            if(val[i] < len) {
                if(query(1, anchor.second, i)==1)swap(anchor.first, anchor.second);
            }
        }
        ord[anchor.first] = -1;
        ord[anchor.second] = -2;
        owo(i, 3, n+1) {
            if(ord[i]!=INF)continue;
            if(val[i] >= len) {
                int k = query(1, anchor.first, i);
                if(k > val[i]) {
                    ord[i] = k;
                }else {
                    ord[i] = -k-1;
                }
            }else {
                ord[i] = query(1, anchor.first, i);
            }
        }
        int mn = 0;
        owo(i, 1, n+1)mn = min(mn, ord[i]);
        cout<<"!";
        owo(i, 1, n+1)cout<<" "<<ord[i]-mn+1;
        cout<<endl;
    }else {
        anchor = anchor2;
        if(len==1) {
            if(query(anchor.first, 1, 2)!=1) {
                swap(anchor.first, anchor.second);
            }
        }
        owo(i, 3, n+1) {
            if(val[i] < len) {
                if(query(2, anchor.second, i)==1)swap(anchor.first, anchor.second);
            }
        }
        ord[anchor.first] = 1+len;
        ord[anchor.second] = 2+len;
        owo(i, 3, n+1) {
            if(ord[i]!=INF)continue;
            if(val[i] >= len) {
                int k = query(2, anchor.first, i);
                if(k > val[i]) {
                    ord[i] = len-k;
                }else {
                    ord[i] = len+k+1;
                }
            }else {
                ord[i] = len - query(2, anchor.first, i);
            }
        }
        int mn = 0;
        owo(i, 1, n+1)mn = min(mn, ord[i]);
        cout<<"!";
        owo(i, 1, n+1)cout<<" "<<ord[i]-mn+1;
        cout<<endl;
        
    }
}
void solve() {
    cin>>n;
    /*owo(i, 1, n+1) {
        cin>>p[i];
    }*/
    memset(ord, INF, sizeof(ord));
    memset(cnt, 0, sizeof(cnt));
    owo(i, 3, n+1) {
        val[i] = query(1, 2, i);
        cnt[val[i]]++;
    }
    ord[1] = 0;
    if(cnt[1] > 1 || (cnt[1]==1 && cnt[n-2]==1)) {
        len = 1;
        osolve();
        return;
    }
    owo(i, 1, n+1) {
        if(cnt[i]==1) {
            len = 2*i;
        }
        if(cnt[i]==2) {
            len = 2*i-1;
        }
        if(cnt[i])break;
    }
    ord[2] = len;
    if(len==3) {
        osolve();
        return;
    }
    vector<int> guys;
    owo(i, 3, n+1) {
        if(val[i]==len-1 || val[i]==len-2)guys.senpai(i);
    }
    ttgl anchor = {guys[0], -1};
    owo(i, 0, guys.size()) {
        owo(j, 0, guys.size()) {
            if(i^j) {
                if(query(1, guys[i], guys[j])==1)anchor = {guys[i], guys[j]};
            }
        }
    }
    if(anchor.second != -1 && val[anchor.first] < val[anchor.second])swap(anchor.first, anchor.second);
    ord[anchor.first] = 1;
    if(anchor.second!=-1)ord[anchor.second] = 2;
    owo(i, 3, n+1) {
        if(ord[i]!=INF) continue;
        if(val[i] >= len) {
            int k = query(1, anchor.first, i);
            if(k > val[i]) {
                ord[i] = k+1;
            }else {
                if(k==len) {
                    if(query(2, anchor.first, i) > len)ord[i] = -k;
                    else ord[i] = k+1;
                }else ord[i] = -k;
            }
        }else {
            ord[i] = query(1, anchor.first, i) + 1;
        }
    }
    int mn = 0;
    owo(i, 1, n+1)mn = min(mn, ord[i]);
    cout<<"!";
    owo(i, 1, n+1)cout<<" "<<ord[i]-mn+1;
    cout<<endl;
}
int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    cin>>T;
    int k;
    owo(tc, 1, T+1) {
        solve();
        cin>>k;
        if(k==-1)exit(0);
    }
    return 0;
}
### Prompt

Please create a solution in cpp 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 target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>
#define owo(i,a, b) for(int i=(a);i<(b); ++i)
#define uwu(i,a, b) for(int i=(a)-1; i>=(b); --i)
#define senpai push_back
#define ttgl pair<int, int>
#define ayaya cout<<"ayaya~"<<endl
 
using namespace std;
using ll = long long;
using ld = long double;
ll MOD;
const ll root = 3;
ll binpow(ll a,ll b){ll res=1;while(b){if(b&1)res=(res*a)%MOD;a=(a*a)%MOD;b>>=1;}return res;}
ll modInv(ll a){return binpow(a, MOD-2);}
const int INF = 0x3f3f3f3f;
const int NINF = 0xc0c0c0c0;
const ll INFLL = 0x3f3f3f3f3f3f3f3f;
const ll NINFLL = 0xc0c0c0c0c0c0c0c0;
const int mxN = 100001;
int res[mxN];
int ord[mxN];
int val[mxN];
int cnt[mxN];
int p[mxN];
int n;
int len;
int query(int a, int b, int c) {
    cout<<"? "<<a<<" "<<b<<" "<<c<<endl;
    int x;
    cin>>x;
    return x;
    /*vector<int> ok = {abs(p[a]-p[b]), abs(p[b]-p[c]), abs(p[a]-p[c])};
    sort(ok.begin(), ok.end());
    return ok[1];*/
}
void osolve() {
    vector<int> guys;
    ord[2] = ord[1] + len;
    owo(i, 3, n+1) {
        if(val[i]==len || (val[i]==len+1 && val[i]==2))guys.senpai(i);
    }
    ttgl anchor = {-1, -1};
    ttgl anchor2 = {-1, -1};
    owo(i, 0, guys.size()) {
        owo(j, 0, guys.size()) {
            if(i^j) {
                if(query(1, guys[i], guys[j])==1)anchor = {guys[i], guys[j]};
                if(query(2, guys[i], guys[j])==1)anchor2 = {guys[i], guys[j]};
            }
        }
    }
    if(anchor.first!=-1) {
        if(len==1) {
            if(query(anchor.first, 1, 2)!=1) {
                swap(anchor.first, anchor.second);
            }
        }
        owo(i, 3, n+1) {
            if(val[i] < len) {
                if(query(1, anchor.second, i)==1)swap(anchor.first, anchor.second);
            }
        }
        ord[anchor.first] = -1;
        ord[anchor.second] = -2;
        owo(i, 3, n+1) {
            if(ord[i]!=INF)continue;
            if(val[i] >= len) {
                int k = query(1, anchor.first, i);
                if(k > val[i]) {
                    ord[i] = k;
                }else {
                    ord[i] = -k-1;
                }
            }else {
                ord[i] = query(1, anchor.first, i);
            }
        }
        int mn = 0;
        owo(i, 1, n+1)mn = min(mn, ord[i]);
        cout<<"!";
        owo(i, 1, n+1)cout<<" "<<ord[i]-mn+1;
        cout<<endl;
    }else {
        anchor = anchor2;
        if(len==1) {
            if(query(anchor.first, 1, 2)!=1) {
                swap(anchor.first, anchor.second);
            }
        }
        owo(i, 3, n+1) {
            if(val[i] < len) {
                if(query(2, anchor.second, i)==1)swap(anchor.first, anchor.second);
            }
        }
        ord[anchor.first] = 1+len;
        ord[anchor.second] = 2+len;
        owo(i, 3, n+1) {
            if(ord[i]!=INF)continue;
            if(val[i] >= len) {
                int k = query(2, anchor.first, i);
                if(k > val[i]) {
                    ord[i] = len-k;
                }else {
                    ord[i] = len+k+1;
                }
            }else {
                ord[i] = len - query(2, anchor.first, i);
            }
        }
        int mn = 0;
        owo(i, 1, n+1)mn = min(mn, ord[i]);
        cout<<"!";
        owo(i, 1, n+1)cout<<" "<<ord[i]-mn+1;
        cout<<endl;
        
    }
}
void solve() {
    cin>>n;
    /*owo(i, 1, n+1) {
        cin>>p[i];
    }*/
    memset(ord, INF, sizeof(ord));
    memset(cnt, 0, sizeof(cnt));
    owo(i, 3, n+1) {
        val[i] = query(1, 2, i);
        cnt[val[i]]++;
    }
    ord[1] = 0;
    if(cnt[1] > 1 || (cnt[1]==1 && cnt[n-2]==1)) {
        len = 1;
        osolve();
        return;
    }
    owo(i, 1, n+1) {
        if(cnt[i]==1) {
            len = 2*i;
        }
        if(cnt[i]==2) {
            len = 2*i-1;
        }
        if(cnt[i])break;
    }
    ord[2] = len;
    if(len==3) {
        osolve();
        return;
    }
    vector<int> guys;
    owo(i, 3, n+1) {
        if(val[i]==len-1 || val[i]==len-2)guys.senpai(i);
    }
    ttgl anchor = {guys[0], -1};
    owo(i, 0, guys.size()) {
        owo(j, 0, guys.size()) {
            if(i^j) {
                if(query(1, guys[i], guys[j])==1)anchor = {guys[i], guys[j]};
            }
        }
    }
    if(anchor.second != -1 && val[anchor.first] < val[anchor.second])swap(anchor.first, anchor.second);
    ord[anchor.first] = 1;
    if(anchor.second!=-1)ord[anchor.second] = 2;
    owo(i, 3, n+1) {
        if(ord[i]!=INF) continue;
        if(val[i] >= len) {
            int k = query(1, anchor.first, i);
            if(k > val[i]) {
                ord[i] = k+1;
            }else {
                if(k==len) {
                    if(query(2, anchor.first, i) > len)ord[i] = -k;
                    else ord[i] = k+1;
                }else ord[i] = -k;
            }
        }else {
            ord[i] = query(1, anchor.first, i) + 1;
        }
    }
    int mn = 0;
    owo(i, 1, n+1)mn = min(mn, ord[i]);
    cout<<"!";
    owo(i, 1, n+1)cout<<" "<<ord[i]-mn+1;
    cout<<endl;
}
int main() {
    //freopen("file.in", "r", stdin);
    //freopen("file.out", "w", stdout);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    cin.tie(0)->sync_with_stdio(0);
    int T = 1;
    cin>>T;
    int k;
    owo(tc, 1, T+1) {
        solve();
        cin>>k;
        if(k==-1)exit(0);
    }
    return 0;
}
```