Description

This is an interactive problem.

There is a 01-string $a$ of length $n$. This 01-string is predetermined before you start querying. You can query the interactor at most $m$ times, and then determine the value of each digit in the $a$ sequence.

You have two types of queries, both of which count toward the number of operations. The formats are as follows:

• ? s: Here $s$ is a string of length $n$ consisting only of the digits 0 and 1. Then, let $t_1 = \sum_{i=1}^{n} [s_i = 1][a_i = 0]$ and $t_2 = \sum_{i=1}^{n} [s_i = 1][a_i = 1]$. The interactor will output the value $t_1 \times t_2$.

• ! s: This indicates that you have determined the value of each digit in the $a$ sequence. You need to represent the $a$ sequence as a 01-string $s$.

  • If for all $i \in [1,n]$, $s_i = a_i$, the interactor will output $1$. If this is the last test case, the judge will give an Accepted result; if it is not the last test case, you need to proceed to the next test case.
  • Otherwise, the interactor will output $0$.
  • Specifically, this operation can be used at most $\boldsymbol{2}$ times. If you use it more than $\boldsymbol{2}$ times, the judge will give a Wrong Answer result.

Input Format

This problem contains multiple test cases per test point.

The first line contains a non-negative integer $T$, the number of test cases.

For each test case, the first line inputs a positive integer $n$. Then, the interaction proceeds as described in the problem description.

You can use the following statements to flush the buffer:

• For C/C++: fflush(stdout);
• For C++: std::cout << std::flush;
• For Java: System.out.flush();
• For Python: stdout.flush();
• For Pascal: flush(output);
• For other languages, please refer to the help documentation of the respective language.

Specifically, for C++, if you use std::endl instead of '\n' when outputting a newline, it will automatically flush the buffer.

Output Format

See the input format.

3
1

1
2

1

0

1
8

0

1

! 0


? 11

! 00

! 01


? 10100001

! 10100001

Hint

Explanation

The sample is only for demonstrating the interaction format and does not guarantee the rationality of the sample output strategy.

This sample has $3$ test cases.

For the first test case, $n = 1$. We guess the final string as 0 and get it right on the first try.

For the second test case, $n = 2$. We first query the product of the counts of 0s and 1s at positions $1$ and $2$ and get $1$. We first guess the final string as 00 and find it is wrong. Then we guess the final string as 01 and find it is correct.

For the third test case, $n = 8$. We first query the product of the counts of 0s and 1s at positions $1$, $3$, and $8$ and get $0$. We first guess the final string as 10100001 and find it is correct.

Scoring Criteria

Let $x$ be the maximum number of queries you use across all test cases in all test points. Then:

• If $x > 1001$, you will get $0$ points.
• If $x = 1001$, you will get $5$ points.
• If $385 \le x \le 1000$, you will get $5 + 90 \times \biggl(1 - \displaystyle\frac{x-385}{1001-385}\biggr)$ points.
• If $x \le 384$, you will get $100$ points.

Data Range

This problem uses bundled testing.

For all data, it is guaranteed that $1 \le T \le 10$, $1 \le n \le 1000$.

Translated by DeepSeek V3.1