CF1617D1.Too Many Impostors (easy version)

This is an interactive problem. The only difference between the easy and hard version is the limit on number of questions.

There are $n$ players labelled from $1$ to $n$. It is guaranteed that $n$ is a multiple of $3$.

Among them, there are $k$ impostors and $n-k$ crewmates. The number of impostors, $k$, is not given to you. It is guaranteed that $\frac{n}{3} \lt k \lt \frac{2n}{3}$.

In each question, you can choose three distinct integers $a$, $b$, $c$ ($1 \le a, b, c \le n$) and ask: "Among the players labelled $a$, $b$ and $c$, are there more impostors or more crewmates?" You will be given the integer $0$ if there are more impostors than crewmates, and $1$ otherwise.

Find the number of impostors $k$ and the indices of players that are impostors after asking at most $2n$ questions.

The jury is adaptive, which means the indices of impostors may not be fixed beforehand and can depend on your questions. It is guaranteed that there is at least one set of impostors which fulfills the constraints and the answers to your questions at any time.

这是一个交互式问题。简单版本与困难版本的唯一区别在于提问次数的限制。

有 $n$ 名玩家，编号从 $1$ 到 $n$。保证 $n$ 是 $3$ 的倍数。

其中，有 $k$ 名冒名顶替者（impostors）和 $n-k$ 名船员（crewmates）。冒名顶替者的数量 $k$ 不会提供给你。保证 $\frac{n}{3} \lt k \lt \frac{2n}{3}$。

在每次提问中，你可以选择三个互不相同的整数 $a$、$b$、$c$（满足 $1 \le a, b, c \le n$），并提出如下问题：“在玩家 $a$、$b$ 和 $c$ 中，是冒名顶替者更多，还是船员更多？” 若冒名顶替者多于船员，你将收到整数 $0$；否则（即船员更多或两者相等），你将收到整数 $1$。

你需要在至多 $2n$ 次提问内，确定冒名顶替者的数量 $k$ 以及所有冒名顶替者的编号。

评测机是自适应的，这意味着冒名顶替者的编号未必预先固定，而可能依赖于你所提出的问题。但保证在任意时刻，均存在至少一组满足约束条件且与你已获回答一致的冒名顶替者集合。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of the test cases follows.

The first and only line of each test case contains a single integer $n$ ($6 \le n \lt 10^4$, $n$ is a multiple of $3$) — the number of players.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^4$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是测试用例的描述。

每个测试用例仅有一行，包含一个整数 $n$（$6 \le n \lt 10^4$，且 $n$ 是 $3$ 的倍数）—— 表示玩家数量。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^4$。

Explanation for example interaction (note that this example only exists to demonstrate the interaction procedure and does not provide any hint for the solution):

For the first test case:

Question "? 1 2 3" returns $0$, so there are more impostors than crewmates among players $1$, $2$ and $3$.

Question "? 3 4 5" returns $1$, so there are more crewmates than impostors among players $3$, $4$ and $5$.

Outputting "! 3 4 1 2" means that one has found all the impostors, by some miracle. There are $k = 3$ impostors. The players who are impostors are players $4$, $1$ and $2$.

For the second test case:

Question "? 7 1 9" returns $1$, so there are more crewmates than impostors among players $7$, $1$ and $9$.

Outputting "! 4 2 3 6 8" means that one has found all the impostors, by some miracle. There are $k = 4$ impostors. The players who are impostors are players $2$, $3$, $6$ and $8$.

示例交互说明（注意：该示例仅用于演示交互流程，不提供任何解题提示）：

对于第一个测试用例：

询问 “? 1 2 3” 返回 $0$，说明玩家 $1$、$2$ 和 $3$ 中，冒名顶替者（impostor）人数多于船员（crewmate）人数。

询问 “? 3 4 5” 返回 $1$，说明玩家 $3$、$4$ 和 $5$ 中，船员人数多于冒名顶替者人数。

输出 “! 3 4 1 2” 表示某人奇迹般地找出了全部冒名顶替者。此时冒名顶替者人数为 $k = 3$，冒名顶替者为玩家 $4$、$1$ 和 $2$。

对于第二个测试用例：

询问 “? 7 1 9” 返回 $1$，说明玩家 $7$、$1$ 和 $9$ 中，船员人数多于冒名顶替者人数。

输出 “! 4 2 3 6 8” 表示某人奇迹般地找出了全部冒名顶替者。此时冒名顶替者人数为 $k = 4$，冒名顶替者为玩家 $2$、$3$、$6$ 和 $8$。