D. Good String Again
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

This is an interactive problem

Yugandhar bought a binary string$$$^\dagger$$$ $$$S$$$ of length $$$n$$$ for Diya's birthday gift. So, he wants Diya to guess any positions of substrings $$$01$$$ and $$$10$$$ respectively. For that, she can ask the following type of query.

  • $$$?$$$ $$$T$$$, where $$$T$$$ is a binary string of length $$$n$$$. In return, Yugandhar will tell the number of $$$0's$$$ in $$$(S \oplus T)$$$, where $$$\oplus$$$ denotes the Bitwise XOR.

Diya got so confused with this task, so please help her to find the required answer within $$$40$$$ queries.

$$$^\dagger$$$ A binary string is a string which only contains $$$0's$$$ and $$$1's$$$.

Input

The first line contains an integer $$$t(1 \le t \le 10^5)$$$, denoting the number of test cases.

For each test case, the only line contains a single integer $$$n$$$ $$$(1 \le n \le 2 \cdot 10^{5})$$$ — the length of the hidden binary string.

It is guaranteed that the sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^{5}$$$.

Interaction

For each test case, the interaction starts with reading $$$n$$$.

Then you are allowed to ask atmost $$$40$$$ queries of the following way

"$$$?$$$ $$$T$$$" ($$$T$$$ is a binary string of length $$$n$$$).

After each one, you should read an integer $$$x$$$ which is equal to the number of $$$0's$$$ in $$$(S \oplus T)$$$, where $$$\oplus$$$ denotes the Bitwise XOR.

When you have found the positions of substrings $$$01$$$ and $$$10$$$ respectively, print a single line "$$$!$$$ $$$i$$$ $$$j$$$" (without quotes), representing $$${S_i}{S_{i+1}}$$$ is equal to $$$01$$$ and $$${S_j}{S_{j+1}}$$$ is equal to $$$10$$$. If there is no $$$01$$$ substring then $$$i = -1$$$, similarly, if there is no $$$10$$$ substring then $$$j = -1$$$. Outputting the answer does not count as a query.

The interactor for this problem is not adaptive: binary string $$$S$$$ is fixed before any queries are made.

After printing a query, do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use:

  • fflush(stdout) or cout.flush() in C++;
  • System.out.flush() in Java;
  • flush(output) in Pascal;
  • stdout.flush() in Python;
  • see the documentation for other languages.
Example
Input
1
4

3

1

1
Output
? 0101

? 1010

? 0110

! 3 -1
Note

In the $$$1^{st}$$$ testcase, the hidden string is $$$0001$$$.

The value of $$$0001$$$ $$$\oplus$$$ $$$0101$$$ is $$$0100$$$ which contains $$$3$$$ $$$0's$$$.