CF2209C.Find the Zero

This is an interactive problem.

You are given an integer $n$. There is a hidden array $a$ of length $2n$. Each integer from $1$ to $n$ appears exactly once in $a$. The rest of the elements are all $0$.

You can make the following type of query:

• Choose two integers $i$ and $j$ ($1 \le i,j \le 2n$, $i \ne j$). The judge will respond with $1$ if $a_i=a_j$, and will respond with $0$ otherwise.

Find any integer $k$ ($1 \le k \le 2n$) such that $a_k=0$ in no more than $n+1$ queries. Note that the interactor is adaptive, which means that the hidden array $a$ may change depending on your queries but will not contradict previous queries.

这是一个交互式问题。

你将得到一个整数 $n$。存在一个长度为 $2n$ 的隐藏数组 $a$。其中，每个从 $1$ 到 $n$ 的整数在 $a$ 中恰好出现一次，其余元素均为 $0$。

你可以执行如下类型的查询：

• 选择两个整数 $i$ 和 $j$（满足 $1 \le i,j \le 2n$ 且 $i \ne j$）。评测系统将返回 $1$（若 $a_i = a_j$），否则返回 $0$。

请在至多 $n+1$ 次查询内，找出任意一个下标 $k$（满足 $1 \le k \le 2n$）使得 $a_k = 0$。注意：该交互器是自适应的，即隐藏数组 $a$ 可能根据你的查询动态变化，但所有变化均不会与之前已给出的查询响应相矛盾。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^3$). The description of the test cases follows.

The first line of each test case contains an integer $n$ ($2 \le n \le 10^4$). The length of the hidden array $a$ will be $2n$.

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

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

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^4$）。隐藏数组 $a$ 的长度为 $2n$。

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

In the first example test case, the hidden array $a$ is $[0,1,0,2]$:

• In the first query, $(i,j)=(1,2)$. Since $a_1=0$, $a_2=1$, $a_1 \ne a_2$, the judge responds with $0$.
• In the second query, $(i,j)=(3,1)$. Since $a_3=0$, $a_1=0$, $a_3 = a_1$, the judge responds with $1$.
• The program reports $k=3$ as an answer. Since $a_3=0$, the answer is correct.

In the second example test case, the hidden array $a$ is $[3,2,0,1,0,0]$:

• In the first query, $(i,j)=(5,6)$. Since $a_5=0$, $a_6=0$, $a_5 = a_6$, the judge responds with $1$.
• In the second query, $(i,j)=(2,4)$. Since $a_2=2$, $a_4=1$, $a_2 \ne a_4$, the judge responds with $0$.
• In the third query, $(i,j)=(1,3)$. Since $a_1=3$, $a_3=0$, $a_1 \ne a_3$, the judge responds with $0$.
• The program reports $k=6$ as an answer. Since $a_6=0$, the answer is correct.

在第一个样例测试用例中，隐藏数组 $a$ 为 $[0,1,0,2]$：

• 在第一次查询中，$(i,j)=(1,2)$。由于 $a_1=0$，$a_2=1$，且 $a_1 \ne a_2$，评测系统返回 $0$。
• 在第二次查询中，$(i,j)=(3,1)$。由于 $a_3=0$，$a_1=0$，且 $a_3 = a_1$，评测系统返回 $1$。
• 程序报告答案 $k=3$。由于 $a_3=0$，该答案正确。

在第二个样例测试用例中，隐藏数组 $a$ 为 $[3,2,0,1,0,0]$：

• 在第一次查询中，$(i,j)=(5,6)$。由于 $a_5=0$，$a_6=0$，且 $a_5 = a_6$，评测系统返回 $1$。
• 在第二次查询中，$(i,j)=(2,4)$。由于 $a_2=2$，$a_4=1$，且 $a_2 \ne a_4$，评测系统返回 $0$。
• 在第三次查询中，$(i,j)=(1,3)$。由于 $a_1=3$，$a_3=0$，且 $a_1 \ne a_3$，评测系统返回 $0$。
• 程序报告答案 $k=6$。由于 $a_6=0$，该答案正确。