Description

注意，本题为交互题。

AsindE 有一个 $k$ 层的满二叉树，满二叉树的根节点编号为 $1$。

$k$ 层的满二叉树有 $2^k - 1$ 个节点，其中每个非叶子节点 $p$ 都有两个儿子节点，其中左儿子节点的编号为 $2 \times p$，右儿子的节点编号为 $2 \times p + 1$。

比如一个层数为 $3$ 的满二叉树为：

为了拷打上次抢了他金币的 slwang，AsindE 在树上标记了一个隐藏节点，让 slwang 找出隐藏节点。slwang 每次可以选择树上的任意一条存在的边将其斩断（被斩断的边不再存在），随后 AsindE 会告诉 slwang 隐藏节点所在连通块（隐藏节点通过存在的边能到达的节点个数，包括它自己）的大小。

slwang 需要在 $2 \times k$ 次操作以内将隐藏节点找出来，否则 AsindE 会将他发配至提瓦特大陆和植物抢空气。为展现自己的慈悲，AsindE 允许 slwang 最后可以选择两个节点（可以相同）作为答案，两个节点中只要有任意一个猜对即可。你能帮助 slwang 解决这个问题吗？

Format

Input

本题有多组测试数据。

第一行一个正整数 $t\ (1 \leqslant t \leqslant 100)$，表示数据组数。

每组数据的第一行一个正整数 $k\ (1\leqslant k \leqslant 40)$，表示满二叉树的层数。

Output

所有隐藏节点在交互开始前就已固定，你的操作对隐藏节点没有影响。

对于每组数据，你可以用不超过 $2 \times k$ 次如下操作找出隐藏节点：

• "? u v" $(1 \leqslant u, v \leqslant 2^k - 1,u \neq v)$。

表示将节点 $u,v$ 之间的边切断，你需要保证 $u,v$ 节点之间存在一条边。每次操作后，你需要从标准输入中读入一个正整数，表示隐藏节点所在连通块的大小。

如果你找到了答案，用如下格式输出单独的一行：

"! u v" $(1 \leqslant u, v \leqslant 2^k - 1)$。

然后处理下一组数据。

如果你在一组数据中进行了多于 $2\times k$ 次操作，或者输出的操作不合法，交互程序将会立即结束，你的程序运行结果将会返回 $\texttt{Wrong Answer}$。

每当你的程序输出一个询问或回答时，请在末尾输出换行符并刷新标准输出的缓冲区，否则你的程序运行结果将会返回 $\texttt{Idleness limit exceeded}$。你可以使用如下方式刷新缓冲区：

• 在 C++ 中：$\texttt{fflush(stdout) 或 cout.flush()}$；
• 在 Java 中：$\texttt{System.out.flush()}$；
• 在 Python 中：$\texttt{stdout.flush()}$；

其他语言请参阅相关文档。

Samples

1
3

6

5

1

? 3 6

? 2 4

? 2 5

! 5 5

Limitation

1s, 256MB for each test case.