Description

Ivan 和 Petr 喜欢玩 仙人掌图 —— 这是一种特殊的图，其中每条边最多属于一个简单环，且图是连通的。允许一对顶点之间存在多条边，也允许自环。

他们发明了以下游戏：

• Petr 秘密地构建一个有 $n$ 个顶点和 $m$ 条边的仙人掌图。这些边被标记为 $1$ 到 $m$。
• Petr 只告诉 Ivan 数字 $m$。
• 然后 Ivan 被允许提出以下形式的问题：
  • 他选择一个边标签的子集 $S$（关于子集的限制见下文），并问：“如果我们只保留标签在 $S$ 中的边（以及所有 $n$ 个顶点），得到的图是否连通？”
  • Petr 必须回答 “yes” 或 “no”。

在最多提出 $8m$ 个问题后，Ivan 必须确定每条边：

1. 这条边是否位于仙人掌图的某个环上；
2. 如果是，该简单环的长度是多少。

在这个问题中，每个自环被视为长度为 $1$ 的简单环，而同一对顶点之间的两条边构成一个长度为 $2$ 的简单环。

然而，Ivan 还很年轻，只认识不超过 $14$ 的数字。因此：

• 如果一条边位于长度不超过 $14$ 的简单环上，他必须输出该确切长度；
• 如果一条边位于长度大于 $14$ 的简单环上，他必须说这条边位于一个 大环 上。

此外，为了避免每次列出很多条边，Ivan 总是询问从之前某个查询使用的边集，或从所有边的集合中，恰好移除一条边所得到的边集。

你能设计一个策略让 Ivan 完成这个任务吗？

Input Format

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$ 是之前某个查询的编号，或为零（查询按提出顺序从 $1$ 开始编号），$q$ 是当前查询之前已提出的查询数量，$e$ 是一条边的标签。

该查询表示一个图，由查询编号 $p$ 中使用的边（如果 $p = 0$ 则表示所有边）去除边 $e$ 后组成。交互器检查该图在考虑 所有原始顶点 时是否连通，并返回一个整数：

• $1$ 如果查询所表示的图是连通的；
• $0$ 如果查询所表示的图不是连通的；
• $-1$ 如果你超出了 $8m$ 个允许的查询，或者边 $e$ 已经从查询 $p$ 使用的边集中被移除了。在这种情况下，你应该终止程序以收到 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
7

0

1

1

1

? 0 1

? 0 3

? 2 4

! -1 3 1 3 2 3 2

Hint

在示例交互中，输入和输出包含空行以使交互器的响应与查询对齐。这些空行在实际的输入和输出中不会出现。

在这个例子中，图有 $5$ 个顶点和 $7$ 条边；边 $1$ 到 $7$，按顺序依次是 $(1,2)$、$(2,3)$、$(3,3)$、$(3,4)$、$(4,5)$、$(2,4)$、$(4,5)$。

:::align{center} :::