E. Punctured Neighborhood
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

There is an unknown sequence $$$B$$$ consisting of $$$0$$$s and $$$1$$$s, with 1-based indexing. You can make multiple queries. In each query, you specify a center $$$m$$$ and a radius $$$r$$$, and the interactor will return the number of $$$1$$$s in the punctured neighborhood of indices $$$[m-r,m+r]\setminus\{m\}$$$ of $$$B$$$. Try to determine the total number of $$$1$$$s in $$$B$$$.

Note that the interval you query must not exceed the boundaries of the sequence itself.

Interaction

There are multiple test cases in this problem.

First, read a line containing a single positive integer $$$T$$$ $$$(1\le T\le1000)$$$, denoting the number of test cases.

For each test case:

  • First read a line containing a single integer $$$n$$$ $$$(4\le n\le1000)$$$, denoting the length of $$$B$$$.
  • To make a query, output a line in the format ? m r and flush the output buffer. It is required that $$$2\le m\le n-1,r\ge1,m-r\ge1,m+r\le n$$$. Then, read a line containing a non-negative integer, denoting the value of $$$\sum_{i=1}^r(B_{m-i}+B_{m+i})$$$.
  • When you have found the answer, output a line in the format ! x and flush the output buffer, where $$$x$$$ represents the total number of $$$1$$$s in $$$B$$$.
  • As an exception, if it is impossible to determine the answer no matter how queries are made, output a line ! -1 and flush the output buffer.

The number of queries for each test case must not exceed $$$35$$$.

Violations such as an incorrect interaction format or exceeding the query limit will result in an undefined verdict.

Example
Input
2
4

1

1

5

4

2
Output


? 2 1

? 3 1

! 2

? 3 2

? 2 1

! 5
Note

The example demonstrates a possible interaction process. The unknown sequences in the two test cases are 1100 and 11111, respectively.

How to flush the output buffer:

  • In C and C++, use fflush(stdout) (if using printf) or cout.flush() (if using cout); Using cout << endl will also flush the buffer in C++.
  • In Python, use stdout.flush();