B. Secret String Patterns
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem.

There is a secret binary string $$$s$$$ of length $$$n$$$. Alice wants to know the answer to the following question: Does there exist an index $$$i$$$ ($$$1\le i \lt n$$$) such that $$$s_i = 0$$$ and $$$s_{i+1} = 1$$$?

To help answer this question, you are allowed to ask queries of the following form: given two integers $$$l$$$ and $$$r$$$ ($$$1\le l\le r\le n$$$), what is the number of $$$1$$$'s among $$$s_{l}, s_{l+1}, \ldots, s_{r}$$$?

Help Alice determine whether the answer to her question is Yes after at most $$$5$$$ queries!

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^3$$$). The description of the test cases follows.

The first and only line of each test case contains a single integer $$$n$$$ ($$$2\le n \le 2\cdot 10^4$$$) —the length of the hidden string $$$s$$$ in this test case.

Interaction

To ask a query, output a line in the following format (do not include quotes):

  • "? l r" ($$$1\le l\le r\le n$$$)

The jury will return the number of $$$1$$$'s among $$$s_{l}, s_{l+1}, \ldots, s_r$$$.

When you are ready to print the answer, output a single line in the following format:

  • If there exists an index $$$i$$$ ($$$1\le i \lt n$$$) such that $$$s_i = 0$$$ and $$$s_{i+1} = 1$$$, output "! YES".
  • Otherwise, output "! NO".

After that, proceed to process the next test case or terminate the program if it is the last test case. Printing the answer does not count as a query.

The interactor is not adaptive, meaning that the hidden string $$$s$$$ will not change in response to queries.

If your program makes more than $$$5$$$ queries for one test case, your program should immediately terminate and receive the verdict Wrong Answer. Otherwise, you can get an arbitrary verdict because your solution will continue to read from a closed stream.

After printing each query do not forget to output the end of line and flush$$$^{\text{∗}}$$$ the output. Otherwise, you will get Idleness limit exceeded verdict.

If, at any interaction step, you read $$$-1$$$ instead of valid data, your solution must exit immediately. This means that your solution will receive Wrong answer because of an invalid query or any other mistake. Failing to exit can result in an arbitrary verdict because your solution will continue to read from a closed stream.

Hacks

To hack, use the following format.

The first line should contain a single integer $$$t$$$ ($$$1\le t\le 10^3$$$) — the number of test cases.

The next $$$t$$$ lines should have exactly three items separated by spaces: $$$n$$$ ($$$2\le n\le 2\cdot 10^4$$$), the single character s, and the binary string (of length $$$n$$$). An example of such a line, corresponding to the first testcase below, is "5 s 10101".

$$$^{\text{∗}}$$$To flush, use:

  • fflush(stdout) or cout.flush() in C++;
  • sys.stdout.flush() in Python;
  • see the documentation for other languages.
Example
Interaction log
< 2
< 5
> ? 1 1
< 1
> ? 1 2
< 1
> ? 1 3
< 2
> ? 1 4
< 2
> ? 1 5
< 3
> ! YES
< 5
> ? 2 5
< 0
> ! NO
Note

In the first test case, the queries here reconstruct the entire string: it is 10101. We can see that $$$i = 2$$$ is a valid index.

In the second test case, note that the only possible secret strings after the queries are 10000 and 00000, neither of which has an index $$$i$$$ where $$$s_i = 0$$$ and $$$s_{i+1} = 1$$$.