这是一个交互式问题。

Randias 有一棵未知的隐藏树，包含 $n$ 个顶点。该树要么是一条链，要么是一颗星形树。Randias 需要确定这棵树是链还是星形树。他可以提出如下形式的问题，但不能超过 $\lceil \frac{n}{2} \rceil + 3$ 次：

• 顶点 $u$ 和顶点 $v$ 之间是否有边 (1 ≤ $u, v$ ≤ $n$, 且 $u \neq v$)？

Randias 需要通过提问来确定树是哪一种。请帮助他提出问题并确定答案。

如果存在一个排列 $p_1, p_2, \dots, p_n$，使得对于每个 $i$ (1 ≤ $i$ < $n$)，树中存在一条边 $(p_i, p_{i+1})$，则该树称为链。在这种情况下，长度为 $n$ 的排列是一个数组，其中 $1$ 到 $n$ 的每个整数恰好出现一次。

如果存在一个顶点 $u$，使得对于每个其他顶点 $v$，树中都有一条边 $(u, v)$，则该树称为星形树。

在这个问题中，交互器是自适应的，这意味着秘密的树并不是预先固定的。相反，交互器可以在交互过程中任意改变树。然而，无论何时，树都将与您获得的所有答案保持一致。

输入格式

每个测试包含多个测试用例。第一行包含一个整数 $t$ (1 ≤ $t$ ≤ 250)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ (4 ≤ $n$ ≤ 1000)，表示顶点的数量。保证所有测试用例中 $n$ 的总和不超过 1000。

交互协议

每个测试用例中最多可以提问 $\lceil \frac{n}{2} \rceil + 3$ 次问题。要提出问题，输出一行形式为“? $u$ $v$” (1 ≤ $u, v$ ≤ $n$ 且 $u \neq v$) 的内容。然后你应当从标准输入中读取响应。

作为响应，交互器将输出一行，包含一个整数：如果顶点 $u$ 和顶点 $v$ 之间有边，则为 1；否则为 0。

当你确定树的类型时，输出一行形式为“! 1” 表示树是一条链，或者“! 2” 表示树是一颗星形树。答案的输出不计入提问的次数限制。

输出答案后，你的程序应该处理下一个测试用例，或者在没有更多测试用例时终止。

每次打印一行后，记得输出换行符并刷新输出。你可以使用 fflush(stdout) 或 cout.flush() (C++)，System.out.flush() (Java)，或 stdout.flush() (Python)。

示例

2 
4 

1 

1 

1 

4 

1 

0 

0 

0

? 1 2 

? 2 3 

? 3 4 

! 1 

? 1 3 

? 2 4 

? 1 2 

? 1 4 

! 2