你已经到达了热门 Roguelike 游戏《艾萨克的键位绑定》（Isaac's Keybindings）的最后一关。你没有遇到 Boss，而是遇到了一位店主，他手中持有一个隐藏的整数数组 $a_1, a_2, \dots, a_n$，其中对于每个 $[1, n]$ 中的 $i$，满足 $0 \le a_i < 2^{30}$。

保证在除样例外的所有测试点中，该数组是随机生成的，即对于每个 $[1, n]$ 中的 $i$，$a_i$ 是 $[0, 2^{30})$ 范围内均匀随机分布的整数。

令 $f(u, v) = a_u \oplus a_{u+1} \oplus \dots \oplus a_v$，其中 $\oplus$ 表示按位异或。

你可以进行如下格式的询问：? u v，其中 $1 \le u \le v \le n$。

询问的回答为：

• 如果 $f(u, v) = 0$，则回答为 $-1$；
• 否则，回答为 $\lfloor \log_2(f(u, v)) \rfloor$。

每次询问需要花费 $\frac{1}{v-u+1}$ 个 robocoin。你初始时拥有 35 个 robocoin，如果你的余额在任何时刻变为负数，你就会失败。请注意，你的 robocoin 余额在任何时刻都不需要是整数。

请在不失败的情况下，求出所有可能的 $\frac{n(n+1)}{2}$ 个询问的答案。

输入格式

每个测试点包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 30$)。接下来是测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ ($1 \le n \le 100$) —— 数组 $a_1, a_2, \dots, a_n$ 的长度。

保证在除样例外的所有测试点中，数组是随机生成的。

本题中恰好有 50 个测试点（包括样例）。样例中 $t = 1$ 且 $n = 3$，而所有其他测试点中 $t = 30$ 且 $n = 100$。

交互格式

对于每个测试用例，首先读取一个整数 $n$。如果你读取到的整数是 $-2$，这意味着前一个测试用例的答案错误，你应该立即退出。

要进行询问，请输出一行格式为 ? u v 的内容，其中 $1 \le u \le v \le n$。

作为对询问的响应，如果你进行了无效的询问（即格式无效，或者你的 robocoin 余额将变为负数），你将收到 $-2$。在这种情况下，你应该立即退出。否则，你将收到该询问的答案。

当你确定了所有 $\frac{n(n+1)}{2}$ 个询问的答案时，请按以下格式输出它们。

输出 $n+1$ 行。第一行必须包含单个字符 !。接下来的 $n$ 行中，第 $i$ 行必须包含 $n - i + 1$ 个整数：分别对应询问 ? i i，? i i+1，...，? i n 的答案。

在输出询问或答案后，请不要忘记输出换行符并刷新输出缓冲区。为此，可以使用：

• 在 C++ 中使用 fflush(stdout) 或 cout.flush()；
• 在 Java 中使用 System.out.flush()；
• 在 Python 中使用 stdout.flush()；
• 其他语言请参阅相应文档。

样例

样例输入 1

1
3

2

-1

1

样例输出 1

? 1 2

? 1 3

? 2 3

!
1 2 -1
2 1
2

说明

样例 1 说明：在样例中，隐藏的数组为 $[a_1, a_2, a_3] = [2, 4, 6]$。

• 首先，你询问 ? 1 2。由于 $f(1, 2) = a_1 \oplus a_2 = 6$，答案为 $\lfloor \log_2(6) \rfloor = 2$。
• 然后，你询问 ? 1 3。由于 $f(1, 3) = a_1 \oplus a_2 \oplus a_3 = 0$，答案为 $-1$。
• 接着，你询问 ? 2 3。由于 $f(2, 3) = a_2 \oplus a_3 = 2$，答案为 $\lfloor \log_2(2) \rfloor = 1$。

现在，即使不知道隐藏的数组，你也可以确定所有可能的 6 个询问的答案。例如，你声称 ? 1 1 的答案是 $1$。

你总共花费了 $\frac{1}{2} + \frac{1}{3} + \frac{1}{2} = \frac{4}{3}$ 个 robocoin，这少于允许的 35 个 robocoin。