D2. 杀手（困难版本）

时间限制：每个测试 $2.5$ 秒
内存限制：$256$ MB

这是本题的困难版本。在此版本中，你必须使用最少的询问次数。只有解决了两个版本的题目，你才能进行 Hack。

这是一个交互式问题。

在墨西哥国家 IOI 训练中，玩一个叫做 "Asesino"（杀手）的游戏是传统，该游戏类似于 "Among Us" 或 "Mafia"。

今天，有 $n$ 名玩家，编号为 $1$ 到 $n$，将扮演以下三种角色玩 "Asesino" 游戏：

• 骑士：骑士总是说真话。
• 恶棍：恶棍总是说谎。
• 内鬼：内鬼是一个大家都以为是骑士、但实际上是恶棍的人。

每个玩家将被分配一个角色。游戏中恰好有一个内鬼，但骑士和恶棍的数量可以是任意值（可能为零）。

作为游戏主持人，你意外忘记了所有人的角色，但你需要找出哪个玩家是内鬼。

为了找出内鬼，你将询问一些问题。在每个问题中，你将选择两名玩家 $i$ 和 $j$（$1 \le i, j \le n$，$i \ne j$），并询问玩家 $i$ 是否认为玩家 $j$ 是骑士。结果如下表所示：

询问者 $i$ 的角色	被问者 $j$ 的角色	回答
骑士	骑士	是
	恶棍	否
	内鬼	是
恶棍	骑士	否
	恶棍	是
	内鬼	否
内鬼	骑士
	恶棍	是
	内鬼	—

例如，右上角的单元格（行“骑士”，列“内鬼”）中的“是”表示当 $i$ 是骑士且 $j$ 是内鬼时的回答。

找出内鬼，使用尽可能少的询问次数。具体地，设 $f(n)$ 为对于 $n$ 名玩家，存在一种策略能够使用最多 $f(n)$ 次询问找出内鬼的最小整数。那么你应该使用最多 $f(n)$ 次询问来找出内鬼。

注意：评测系统是自适应的：玩家的角色在开始时并不固定，可能会根据你的问题而改变。但是，保证存在一个与之前所有问题一致的角色分配，且符合本题的约束条件。

---

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$3 \le n \le 10^5$），表示玩游戏的人数。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

---

交互格式

要询问一个问题，请按以下格式输出一行：

? i j

其中 $1 \le i, j \le n$，$i \ne j$ —— 询问玩家 $i$ 是否认为玩家 $j$ 是骑士。

评测系统会输出 1 表示玩家 $i$ 认为玩家 $j$ 是骑士，输出 0 表示否。

当你确定内鬼是谁后，按以下格式输出一行：

! i

其中 $1 \le i \le n$ —— 内鬼是玩家 $i$。

注意：回答不计入 $f(n)$ 次询问的限制。

如果你输出了无效内容、使用了超过 $f(n)$ 次询问或错误地确定了内鬼，评测系统将返回 -1，你将收到 Wrong Answer 判定。收到 -1 后，你的程序必须立即终止。否则，你可能会收到任意判定，因为你的程序可能正在从已关闭的流中读取。

每次输出查询后，不要忘记输出换行并刷新输出缓冲区。否则，你会收到 Idleness limit exceeded 错误。为此，请使用：

• C++：fflush(stdout) 或 cout.flush()
• Java：System.out.flush()
• Python：sys.stdout.flush()
• Rust：std::io::stdout().flush()
• 其他语言请参阅文档。

---

Hack 格式

对于 Hack，请使用以下格式：

第一行包含一个整数 $t$ —— 测试用例数量。

每个测试用例的第一行包含整数 $n$ 后跟字符串 "manual"。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-1 \le a_i \le 1$）—— 每个玩家的角色。$1$ 表示骑士，$0$ 表示恶棍，$-1$ 表示内鬼。必须恰好有一个内鬼，即恰好有一个下标 $i$ 使得 $a_i = -1$。

例如，示例输入的 Hack 格式为：

2
7 manual
0 1 0 -1 0 1 0
4 manual
0 1 -1 0

---

示例

输入

2
7

1

0

0

1

1

0

0

4

0

1

1

1

输出

? 1 3

? 7 6

? 2 5

? 6 2

? 4 5

? 4 6

? 1 4

! 4

? 1 2

? 2 3

? 3 4

? 4 1

! 3

---

注意

请注意，示例测试用例并不代表询问问题的最优策略，仅用于演示交互格式。具体来说，我们无法从示例中询问的问题确定内鬼是谁。

在第一个测试用例的示例中，索引 $2$ 和 $6$ 的玩家是骑士，索引 $1$、$3$、$5$ 和 $7$ 的玩家是恶棍，内鬼在索引 $4$。以下是对所问问题的解释：

• 第一个查询：玩家 $i$ 是恶棍，玩家 $j$ 是恶棍。回答是“是”，因为恶棍总是说谎。
• 第二个查询：玩家 $i$ 是恶棍，玩家 $j$ 是骑士。回答是“否”，因为恶棍总是说谎。
• 第三个查询：玩家 $i$ 是骑士，玩家 $j$ 是恶棍。回答是“否”，因为骑士总是说真话。
• 第四个查询：玩家 $i$ 是骑士，玩家 $j$ 是骑士。回答是“是”，因为骑士总是说真话。
• 第五个查询：玩家 $i$ 是内鬼，玩家 $j$ 是恶棍。回答是“是”，因为内鬼总是说谎。
• 第六个查询：玩家 $i$ 是内鬼，玩家 $j$ 是骑士。回答是“否”，因为内鬼总是说谎。
• 第七个查询：玩家 $i$ 是恶棍，玩家 $j$ 是内鬼。回答是“否”，因为恶棍总是说谎，且恶棍认为内鬼是骑士。