CF750F.New Year and Finding Roots

This is an interactive problem. In the interaction section below you will find the information about flushing the output.

The New Year tree of height h is a perfect binary tree with vertices numbered 1 through 2_h_ - 1 in some order. In this problem we assume that h is at least 2. The drawing below shows one example New Year tree of height 3:

Polar bears love decorating the New Year tree and Limak is no exception. To decorate the tree, he must first find its root, i.e. a vertex with exactly two neighbours (assuming that h ≥ 2). It won't be easy because Limak is a little bear and he doesn't even see the whole tree. Can you help him?

There are t testcases. In each testcase, you should first read h from the input. Then you can ask at most 16 questions of format "? x" (without quotes), where x is an integer between 1 and 2_h_ - 1, inclusive. As a reply you will get the list of neighbours of vertex x (more details in the "Interaction" section below). For example, for a tree on the drawing above after asking "? 1" you would get a response with 3 neighbours: 4, 5 and 7. Your goal is to find the index of the root y and print it in the format "! y". You will be able to read h for a next testcase only after printing the answer in a previous testcase and flushing the output.

Each tree is fixed from the beginning and it doesn't change during your questions.

这是一个交互式问题。在下方的“交互”部分中，你将找到有关刷新输出的信息。

高度为 $h$ 的新年树是一棵完美二叉树，其顶点编号为 $1$ 到 $2^h - 1$（以某种顺序）。在本题中，我们假设 $h \geq 2$。下图展示了一棵高度为 $3$ 的新年树示例：

北极熊们热衷于装饰新年树，而 Limak 也不例外。为了装饰这棵树，他必须首先找出它的根节点，即恰好有两个邻居的顶点（假设 $h \geq 2$）。但这并不容易，因为 Limak 是一只小熊，甚至无法看到整棵树。你能帮他吗？

共有 $t$ 组测试数据。对每组测试数据，你应首先从输入中读取 $h$。随后，你最多可提出 $16$ 个形如 ? x（不含引号）的问题，其中 $x$ 是一个介于 $1$ 和 $2^h - 1$（含端点）之间的整数。作为回应，你将收到顶点 $x$ 的所有邻居列表（更多细节见下方“交互”部分）。例如，对上图所示的树，若提问 ? 1，你将收到包含 $3$ 个邻居的响应：4, 5, 7。你的目标是找出根节点的索引 $y$，并以 ! y 的格式输出。只有在上一组测试数据中输出答案并刷新输出后，你才能读取下一组测试数据的 $h$。

每棵树在初始时即已固定，在你提问过程中不会发生任何变化。

The first line of the input contains a single integer t (1 ≤ t ≤ 500) — the number of testcases.

At the beginning of each testcase you should read from the input a single integer h (2 ≤ h ≤ 7) — the height of the tree. You can't read the value of h in a next testcase until you answer a previous testcase.

输入的第一行包含一个整数 $t$（$1 \le t \le 500$）—— 测试用例的数量。

对于每个测试用例，你应首先从输入中读取一个整数 $h$（$2 \le h \le 7$）—— 树的高度。在回答完前一个测试用例之前，你不能读取下一个测试用例中的 $h$ 值。

In the first sample, a tree corresponds to the drawing from the statement.

In the second sample, there are two two testcases. A tree in the first testcase has height 2 and thus 3 vertices. A tree in the second testcase has height 4 and thus 15 vertices. You can see both trees on the drawing below.

在第一个样例中，树对应于题目描述中的图示。

在第二个样例中，包含两个测试用例。第一个测试用例中的树高度为 $2$，因此有 $3$ 个顶点；第二个测试用例中的树高度为 $4$，因此有 $15$ 个顶点。您可在下方图示中看到这两棵树。