Ivan 和 Petr 喜欢玩仙人掌——这是一种特殊的无向连通图，其中每条边最多属于一个简单环。允许存在重边和自环。
他们发明了以下游戏：
- Petr 秘密构建了一个包含 $n$ 个顶点和 $m$ 条边的仙人掌。边从 $1$ 到 $m$ 进行编号。
- Petr 只告诉 Ivan 边数 $m$。
- 然后，Ivan 可以提出以下形式的问题：
- 他选择一个边编号的子集 $S$（关于子集的限制见下文），并询问：“如果我们只保留编号在 $S$ 中的边（以及所有 $n$ 个顶点），得到的图是否连通？”
- Petr 必须回答“是”或“否”。
在最多提问 $8m$ 次后，Ivan 必须确定每条边：
- 该边是否位于仙人掌的某个环上；
- 如果是，该简单环的长度是多少。
在本题中，每个自环被视为长度为 1 的简单环，同一对顶点之间的两条重边形成长度为 2 的简单环。
然而，Ivan 还很年轻，只认识不超过 14 的数字。因此：
- 如果一条边位于长度最多为 14 的简单环上，他必须输出该环的确切长度；
- 如果一条边位于长度大于 14 的简单环上，他必须说明该边位于一个大环上。
此外，为了避免每次都要列出大量的边，Ivan 总是询问一个边集，该边集是通过从之前某次询问所使用的边集（或所有边的集合）中恰好移除一条边而得到的。
你能设计一个策略来帮助 Ivan 完成这个任务吗？
输入格式
每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 100$)。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数 $m$ ($1 \le m \le 10^4$) —— 仙人掌中的边数。
保证所有测试用例中 $m$ 的总和不超过 $10^4$。
交互格式
要进行询问，请按以下格式输出一行（不包含引号）：
? p e($0 \le p \le q$；$1 \le e \le m$)，其中 $p$ 是之前某次询问的编号或为 0（询问按提问顺序从 1 开始编号），$q$ 是在当前询问之前已进行的询问次数，$e$ 是一条边的编号。
该询问表示一个图，它由第 $p$ 次询问中所使用的边集（如果 $p = 0$ 则为所有边的集合）中移除边 $e$ 后得到。交互器会检查在考虑所有原始顶点时该图是否连通，并返回一个整数：
- 如果询问所表示的图是连通的，返回
1； - 如果询问所表示的图是不连通的，返回
0； - 如果你超过了 $8m$ 次允许的询问次数，或者边 $e$ 已经在第 $p$ 次询问所使用的边集中被移除了，返回
-1。在这种情况下，你应该终止程序以获得“答案错误（Wrong Answer）”的评测结果。
当你找到答案后，按以下格式输出一行：
! e_1 e_2 ... e_m（对所有 $i$，$-1 \le e_i \le 14$），
其中：
- 如果 $e_i$ 为正数，则第 $i$ 条边属于一个长度恰好为 $e_i$ 的简单环；
- 如果 $e_i = 0$，则第 $i$ 条边属于一个大环（长度大于 14 的简单环）；
- 如果 $e_i = -1$，则第 $i$ 条边不属于任何环。
随后交互器会返回一个整数：
- 如果你的答案正确，返回
1。此时应继续处理下一个测试用例，如果这是最后一个测试用例，则终止程序。 - 如果你的答案错误，返回
-1。在这种情况下，你应该终止程序以获得“答案错误（Wrong Answer）”的评测结果。
交互器是非自适应的，这意味着图在您进行任何询问之前就已经确定。
样例
输入样例 1
1 7 0 1 1 1
输出样例 1
? 0 1 ? 0 3 ? 2 4 ! -1 3 1 3 2 3 2
说明
在样例交互中，输入和输出中包含空行以便将交互器的响应与询问对齐。这些空行在实际的输入和输出中并不会出现。
在此样例中，图有 5 个顶点和 7 条边；边 1 到 7 依次为 $(1, 2)$，$(2, 3)$，$(3, 3)$，$(3, 4)$，$(4, 5)$，$(2, 4)$，$(4, 5)$。