E. Broken Queries

每个测试用例时间限制：$2$ 秒 每个测试用例内存限制：$256$ 兆字节

你，一个造物被巨龙摧毁的法师，决心用魔法范围追踪器追捕它。但你似乎被戏弄了……

本题是交互题。

存在一个长度为 $n$ 的隐藏二进制数组 $a$（$n$ 是 $2$ 的幂），以及一个隐藏整数 $k$（$2 \le k \le n-1$）。数组 $a$ 中恰好有一个 $1$，其余元素均为 $0$。 对于两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），定义区间和：

$$s(l,r) = a_l + a_{l+1} + \dots + a_r$$

你有一个魔法装置，可以接收区间并返回区间和，但当区间长度大于等于 $k$ 时，它会返回相反的结果。 形式化地说，每次查询你可以输入一对整数 $[l,r]$（满足 $1 \le l \le r \le n$），装置会按照以下规则返回 $0$ 或 $1$：

• 若 $r-l+1 < k$，返回 真实值 $s(l,r)$；
• 若 $r-l+1 \ge k$，返回 取反值 $1-s(l,r)$。

请你使用不超过 $33$ 次查询，找出隐藏的整数 $k$。

该装置非自适应：隐藏的数组 $a$ 和整数 $k$ 在交互开始前就已固定，不会在交互过程中改变。

---

交互格式

本题包含多组测试用例。

1. 第一行输入测试用例数量 $t$（$1 \le t \le 500$）。
2. 每组测试用例的格式：
   • 第一行输入一个正整数 $n$（$4 \le n \le 2^{30}$）—— 隐藏数组的长度。保证 $n$ 是 $2$ 的幂，即存在非负整数 $m$ 使得 $n=2^m$。

查询方式

你可以按照以下格式发起查询： 输出一行 ? l r，其中 $1 \le l \le r \le n$。 随后读取一个整数（$0$ 或 $1$），即装置的返回结果。

回答方式

当你确定答案后，输出一行 ! k。 输出答案不计入查询次数，之后程序继续处理下一组测试用例。

重要要求

每次输出查询/答案后，必须换行并刷新输出缓冲区，否则会出现超时错误。 如果在任意交互步骤中，你读到的结果是 $-1$（而非合法的 $0/1$），你的程序必须立即退出。这代表你的查询无效或出现了其他错误，若不退出会导致未知评测结果。

---

造数据格式（Hacks）

造数据格式如下：

1. 第一行输入一个整数 $t$（$1 \le t \le 100$）。
2. 每组测试用例仅一行，包含三个整数 $n, p, k$：
   • $n$：隐藏数组长度（$4 \le n \le 2^{30}$，且为 $2$ 的幂）；
   • $p$：数组中唯一 $1$ 的位置（$1 \le p \le n$）；
   • $k$：隐藏的整数（$2 \le k \le n-1$）。

---

刷新输出的方法

• C++：fflush(stdout) 或 cout.flush()
• Python：sys.stdout.flush()
• 其他语言请参考对应文档。

---

样例输入

2
8

0

0

1

0
4

1

0

样例输出

? 3 5
? 1 8
? 4 8
? 3 8
! 6
? 3 3
? 3 4
! 2

---

样例解释

1. 第一组测试用例 $k=6$，隐藏数组中 $1$ 的位置是 $6$，即 $a = [0,0,0,0,0,1,0,0]$。

   • 查询 $[3,5]$：长度 $3 < k$，装置返回正确结果。$6$ 不在区间内，结果为 $0$；
   • 查询 $[1,8]$：长度 $8 \ge k$，装置返回取反结果，最终为 $0$；
   • 查询 $[4,8]$：长度 $5 < k$，装置返回正确结果 $1$；
   • 查询 $[3,8]$：长度 $6 \ge k$，装置返回取反结果 $0$。 最终输出答案 $6$，正确。

2. 第二组测试用例 $k=2$，隐藏数组中 $1$ 的位置是 $3$，即 $a = [0,0,1,0]$。

注：样例中的解法不一定能通过现有信息确定 $k$，仅作格式演示。