当前没有测试数据。

E. Kachina 最爱的二进制字符串 每次测试的时间限制：2 秒
每次测试的内存限制：256 兆字节

这是一个交互式问题。

Kachina 向你发起挑战，要求你猜出她最喜欢的长度为 $n$ 的二进制字符串 $s$。
她定义 $f(l, r)$ 为子串 $s_l s_{l+1} \dots s_r$ 中 子序列 $01$ 的数量。
两个子序列被认为是不同的，如果它们是由原字符串中删除不同位置的字符得到的，即使产生的子序列由相同的字符组成。

为了确定 $s$，你可以问一些问题。在每个问题中，你可以选择两个索引 $l$ 和 $r$（$1 \le l < r \le n$），并询问她 $f(l, r)$ 的值。

在问了不超过 $n$ 个问题后，确定并输出 $s$。
然而，有可能 $s$ 无法被确定。在这种情况下，你需要报告 $IMPOSSIBLE$。

形式化地说，如果无论如何提问，在问了 $n$ 个问题后，总是有多种可能的 $s$ 字符串，则 $s$ 是无法确定的。注意，如果你在存在一种不超过 $n$ 次询问的唯一确定二进制字符串的方法时报告 $IMPOSSIBLE$，将会得到 $Wrong Answer$。

---

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

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^4$）—— 字符串 $s$ 的长度。

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

---

交互
要问一个问题，请按如下格式输出一行（不要加引号）：

? l r

其中 $1 \le l < r \le n$。
评审会返回一个整数 $f(l, r)$。

当你准备好输出答案时，输出一行，格式如下：

• 如果 $s$ 无法被确定，则输出 $! IMPOSSIBLE$
• 否则输出 $! s$

之后，继续处理下一个测试用例，或者如果是最后一个测试用例则终止程序。输出答案不算作一次查询。

交互器是非自适应的，意思是答案在参与者提问之前就已经确定，并且不依赖于参与者所提的问题。

如果你的程序对一个测试用例提出的问题超过 $n$ 次，你的程序应立即终止，以得到 $Wrong Answer$。否则，你可能会因为试图从已关闭的流中读取而得到任意裁决。

在每次查询后，不要忘记输出换行并刷新输出缓冲区。否则，你可能会得到 $Idleness limit exceeded$。
为此，请使用：

• $C++：fflush(stdout)$ 或 $cout.flush()$
• $Java：System.out.flush()$
• $Pascal：flush(output)$
• $Python：stdout.flush()$
• 其他语言请查看相应文档。

---

Hack 格式
若要提交 $Hack$，请使用以下格式：

第一行包含一个整数 $t$（$1 \le t \le 10^3$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^4$）—— 字符串 $s$ 的长度。

接下来的一行包含 $s$，一个长度为 $n$ 的二进制字符串。

所有测试用例的 $n$ 之和不超过 $10^4$。

---

示例

输入

2
5

4

0

1

2

2

0

输出

? 1 5

? 2 4

? 4 5

? 3 5

! 01001

? 1 2

! IMPOSSIBLE

注释
在第一个测试用例中：

• 第一次查询中，你询问 Kachina $f(1,5)$ 的值，她回答 $4$。
• 第二次查询中，你询问 $f(2,4)$。因为字符串 $100$ 中没有 $01$ 子序列，她回答 $0$。

在问了 $4$ 个问题后，你报告 $s$ 为 $01001$，答案正确。

在第二个测试用例中：

• 第一次查询中，你询问 $f(1,2)$，她回答 $0$。注意这是你唯一可以问的不同问题。

但注意，字符串 $00$ 和 $11$ 的答案都是 $0$，无法区分两者。因此我们报告 $IMPOSSIBLE$。

请注意，该示例仅用于演示交互格式。不能保证所提供的查询是最优的或能唯一确定答案。不过可以证明，存在不超过 $5$ 次查询的序列，可以唯一确定第一个样例的答案。