题目描述

这是一道交互题。

有一个未知序列 $B$，元素是 $0$ 或 $1$，下标从 $1$ 开始。你可以进行多次询问，每次询问指定中心 $m$ 以及半径 $r$，交互器将返回 $B$ 的下标去心邻域 $[m-r,m+r]\setminus\{m\}$ 内 $1$ 的个数。尝试确定 $B$ 中一共有多少个 $1$。

注意，你询问的区间不能超出序列本身的边界。

交互方式

本题有多组测试数据。

首先读入一行，仅包含一个正整数，表示数据组数 $T (1\le T\le 1000)$。

对于每组数据：

• 首先读入一行，仅包含一个整数 $n$ ($4\le n\le 1000$)，表示 $B$ 的长度。
• 发起询问时，需要以 ? m r 的格式输出一行并清空缓冲区，要求 $2\le m\le n-1,r\ge 1,m-r\ge 1,m+r\le n$。然后读入一行，包含一个非负整数，表示 $\sum_{i=1}^r(B_{m-i}+B_{m+i})$ 的值。
• 当你确定答案后，以 ! x 的格式输出一行并清空缓冲区，其中 $x$ 表示 $B$ 中 $1$ 的个数。
• 特别地，若无论如何询问都不可能确定答案，输出一行 ! -1 并清空缓冲区。

每组数据的询问次数不能超过 $35$。

任何不符合交互要求的输出，包括交互格式错误、超出交互次数限制等，都会导致未定义的运行结果。

样例

2
4

1

1

5

4

2

? 2 1

? 3 1

! 2

? 3 2

? 2 1

! 5

提示

样例展示了一个可能的交互过程，两组数据中的未知序列分别为 1100 和 11111。

如何清空缓冲区：

• 在 C 和 C++ 中，使用 fflush(stdout)（如果你使用 printf）或 cout.flush()（如果你使用 cout）。
• 在 Python 中，使用 stdout.flush()。
• 特别地，在 C++ 中，使用 cout<<endl 会自动清空缓冲区。