This is an interactive problem.

You are given an unknown binary string $$$s$$$$$$^{\text{∗}}$$$ of length $$$n$$$. The function $$$f(l, r)$$$ is defined as the number of distinct elements in the array $$$a$$$ formed by the following operation:

Let $$$S$$$ be the substring $$$s_l s_{l+1} \ldots s_r$$$. Let $$$m$$$ be the length of the substring.
We start with an empty array $$$a$$$.
For the $$$i$$$-th $$$(0 \le i \lt m)$$$ left cyclic rotation$$$^{\text{†}}$$$ of $$$S$$$, let's denote the number of inversions$$$^{\text{‡}}$$$ as $$$x_{i}$$$.
For every $$$i$$$ such that $$$0 \le i \lt m$$$, append $$$x_{i} \mbox{ mod } m$$$ to the array $$$a$$$, where $$$u \mbox{ mod } v$$$ denotes the remainder of dividing $$$u$$$ by $$$v$$$.

To determine $$$s$$$, you can ask some questions. In each question, you can choose $$$2$$$ integers $$$l$$$ and $$$r$$$ ($$$1 \le l \le r \le n$$$) and get the value of $$$f(l, r)$$$. Asking each query incurs a cost of $$$\dfrac{n}{r-l+1}$$$. Note that the cost does not necessarily have to be an integer.

You have to determine the hidden binary string while keeping the total cost of queries atmost $$$\mathbf{max(30,3\cdot n)}$$$. You are allowed to make at most $$$\mathbf{2}$$$ guesses.

$$$^{\text{∗}}$$$A binary string only contains characters $$$\texttt{0}$$$ and $$$\texttt{1}$$$.

$$$^{\text{†}}$$$Let there be a binary string $$$s \; = \; s_{1}s_{2}\cdots s_{n}$$$. The $$$k$$$-th left cyclic rotation of $$$s$$$ is defined as $$$t_{k} \; = \; s_{k+1}s_{k+2}\cdots s_{n}s_{1}s_{2}\cdots s_{k}$$$.

$$$^{\text{‡}}$$$Let there be a string $$$s \; = \; s_{1}s_{2}\cdots s_{n}$$$. The number of inversions of $$$s$$$ is defined as the number of pairs of indices $$$i,j \; (1 \le i \lt j \le n)$$$, such that $$$s_{i} \gt s_{j}$$$.

Input

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

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 3000$$$) — the length of the unknown string $$$s$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3000$$$.

Interaction

To ask a question, output a line in the following format (without quotes)

"$$$\texttt{? l r}$$$" ($$$1 \leq l \leq r \leq n$$$)

The jury will return an integer $$$f(l, r)$$$.

For guessing a string $$$s$$$ (length of $$$s$$$ must be $$$n$$$), output a single line in the following format (without quotes)

"$$$\texttt{! s}$$$"

The jury will return 1 if the guess is correct or 0 if the guess is incorrect.

Guessing a string does not count as a query.

After that, if your string is correct, proceed to the next test case or terminate the program if it was the last test case.

The interactor is not adaptive, meaning that the answer is known before the participant asks the queries and doesn't depend on the queries asked by the participant.

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 make a hack, use the following format.

The first line should contain a single integer $$$t$$$ ($$$1 \leq t \leq 100$$$) — the number of test cases.

The first line of each test case should contain $$$n$$$ ($$$2 \le n \le 3000$$$), the length of $$$s$$$.

The second line of each test case should contain $$$s$$$, a binary string of length $$$n$$$.

The sum of $$$n$$$ over all test cases should not exceed $$$3000$$$.

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

fflush(stdout) or cout.flush() in C++;
sys.stdout.flush() in Python;
see the documentation for other languages.

Note

In the example interaction, the input and output contain empty lines to align interactor responses with queries. These empty lines do not appear in the actual input and output.

In the first test case, the hidden string is $$$s =$$$ 00000. Here, since 0 cannot create any inversion, the array $$$a$$$ will always be $$$[0]$$$ for all substrings. Hence $$$f(l, r)$$$ returns $$$1$$$ for all queries.

Here we made $$$3$$$ queries.

The first query is $$$f(1,5)$$$ which returns 1 — the cost of this query is $$$\dfrac{5}{5-1+1} = 1$$$.

The second query is $$$f(2,5)$$$, which returns 1 — the cost of this query is $$$\dfrac{5}{5-2+1} = \dfrac{5}{4}$$$.

The third query is $$$f(3,5)$$$, which returns 1 — the cost of this query is $$$\dfrac{5}{5-3+1} = \dfrac{5}{3}$$$.

The total cost after all these queries $$$ = 1 + \dfrac{5}{4} + \dfrac{5}{3} = \dfrac{47}{12}$$$ which is less than $$$\max(30, 3\cdot n) = 30$$$.

After this, we guess $$$s =$$$ 00000, for which the interactor returns $$$1$$$, indicating correct guess. We then move to the next test case.

In the second test case, the hidden string is $$$s =$$$ 001.

We make the query $$$f(1,3)$$$, which returns 3. The cost of this query is $$$\dfrac{3}{3-1+1} = 1$$$.

The total cost of the query is $$$1$$$ which is less than $$$\max(30, 3\cdot n) = 30$$$.

We then guess 100, for which the interactor returns 0, indicating it is incorrect.

We guess 001, for which the interactor returns 1, indicating our guess is correct. We then move to the next test case.

For the third test case, the hidden string is $$$s = $$$ 10101010.

✓	#	Name		✎	Rating↕	Solved↕
	2210E	Binary Strings are Simple? constructive algorithms implementation interactive number theory			2700	369
	1592D	Hemose in ICPC ? binary search dfs and similar implementation interactive math number theory trees			2300	2.7k

Problemset