P14033 【MX-X20-T7】「FAOI-R7」Subset Product

**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.**

**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

See the input format.

### 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*