CF1634D.Finding Zero

This is an interactive problem.

We picked an array of whole numbers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$) and concealed exactly one zero in it! Your goal is to find the location of this zero, that is, to find $i$ such that $a_i = 0$.

You are allowed to make several queries to guess the answer. For each query, you can think up three distinct indices $i, j, k$, and we will tell you the value of $\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k)$. In other words, we will tell you the difference between the maximum and the minimum number among $a_i$, $a_j$ and $a_k$.

You are allowed to make no more than $2 \cdot n - 2$ queries, and after that you have two tries to guess where the zero is. That is, you have to tell us two numbers $i$ and $j$ and you win if $a_i = 0$ or $a_j = 0$.

Can you guess where we hid the zero?

Note that the array in each test case is fixed beforehand and will not change during the game. In other words, the interactor is not adaptive.

这是一个交互式问题。

我们选定一个由非负整数构成的数组 $a_1, a_2, \ldots, a_n$（其中 $0 \le a_i \le 10^9$），并在其中恰好隐藏了一个零！你的目标是找出这个零的位置，即找到满足 $a_i = 0$ 的下标 $i$。

你可以进行若干次查询来猜测答案。每次查询中，你需要指定三个互不相同的下标 $i, j, k$，我们将返回 $\max(a_i, a_j, a_k) - \min(a_i, a_j, a_k)$ 的值。换言之，我们将告诉你 $a_i$、$a_j$ 和 $a_k$ 中最大值与最小值之间的差。

你最多可进行 $2 \cdot n - 2$ 次查询；此后你有两次机会来猜测零的位置。也就是说，你必须给出两个下标 $i$ 和 $j$；若 $a_i = 0$ 或 $a_j = 0$，则你获胜。

你能猜出我们把零藏在哪儿了吗？

注意：每个测试用例中的数组在游戏开始前就已固定，且在整个过程中不会改变。换句话说，交互器是非自适应的（non-adaptive）。

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

The first and only line of each test case contains an integer $n$ ($4 \le n \le 1000$) — the length of the array that we picked.

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

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

每个测试用例仅有一行，包含一个整数 $n$（$4 \le n \le 1000$）——即我们所选数组的长度。

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

Array from sample: $[1, 2, 0, 3]$.

来自样例的数组：$[1, 2, 0, 3]$。