总共有\(n\) (\(3 \le n \le 1500\)) 个点，比较直观的一个思路就是，先取其中的三个点，然后如果说有点在这个三角形的内部，那我就去接着查，但是这么做是线性的算法，最多能执行到\(1500\)次，远超过题目上限\(75\)次。
然后也没有什么比较好的方法可以优化，突然想到了随机化（其实正解就是随机化，雾）。
下面给出证明：
设当前没有被查询的点有\(c\)个，那么每次有\(\frac{1}{3}\)的概率取到点数小于\(\frac{c-1}{3}\)的那部分，如果每次都取到这一部分，只需要最多\(\left \lfloor {\log_3(n)} \right \rfloor +1 \le 7\)次就可以找到答案，但是不能够保证每次都取到。
再抽象化一下问题模型，这个随机取点的问题就相当于你做了\(75\)次操作，每次有\(\frac{1}{3}\)的概率抽到目标，问你至少7次抽到目标的概率是多少。
那么这个就是一个二项分布概率模型，那么失败的概率为\(q \approx \sum_{i=68}^{75} \left( C_{75}^{i} \times \left(\frac{1}{3}\right)^{75-i} \times \left(\frac{2}{3}\right)^{i} \right) \leq 8.1 \cdot 10^{-5}\)显然这个概率极小
#include <bits/stdc++.h>
using namespace std;
/**/
mt19937 rd(time(nullptr));
void sol() {int n;cin>>n;int a=1,b=2,c=3;while(1){cout<<"? "<<a<<' '<<b<<' '<<c<<'\n';cout.flush();int p;cin>>p;if(!p){cout<<"! "<<a<<' '<<b<<' '<<c<<'\n';cout.flush();break;}int x=rd()%3;if(x==0) a=p;else if(x==1) b=p;else c=p;}
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {sol();}return 0;
}