子集乘积 - Problem

题目描述

这是一道交互题。

有一个长度为 $n$ 的 $01$ 字符串 $a$，这个 $\boldsymbol{01}$ 字符串是在你开始询问前就预先确定的。你可以询问交互库至多 $m$ 次，然后求出 $a$ 序列每个数字的值。

你有两种询问，两种询问都计入操作次数，格式如下：

? s，其中 $s$ 为一个仅含 01 两种数字的长度为 $n$ 的字符串 $s$，然后，设 $t_1 = \sum_{i=1}^{n} [s_i = 1][a_i = 0]$，$t_2 = \sum_{i=1}^{n} [s_i = 1][a_i = 1]$，则交互库会输出 $t_1 \times t_2$ 的值。
! s，表示你已经知道了 $a$ 序列每个数字的值，你需要以一个 01 字符串 $s$ 表示 $a$ 序列。
- 若对于所有 $i \in [1,n]$，$s_i=a_i$，则交互库会输出 $1$。若这是最后一组测试数据，评测机会给出 Accepted 的结果；若这不是最后一组测试数据，则你需要继续进行下一组测试数据；
- 否则，交互库会输出 $0$。
- 特别地，此操作至多使用 $\boldsymbol 2$ 遍，若你使用了 $\boldsymbol{> 2}$ 遍此操作评测机会给出 Wrong Answer 的结果。

本题每个测试点内含有多组数据。

第一行一个非负整数 $T$ 表示测试数据组数。

之后对于每组测试数据，第一行输入一个正整数 $n$，之后进行交互，交互格式见题目描述。

你可以使用如下语句来清空缓冲区：

特别地，对于 C++ 语言，在输出换行时如果你使用 std::endl 而不是 '\n'，也可以自动刷新缓冲区。

见输入格式。

样例仅供展示交互格式，不保证样例输出策略的合理性。

该样例共有 $3$ 组测试数据。

对于第一组测试数据，$n = 1$，我们猜测最终字符串为 0，一次猜对了。

对于第二组测试数据，$n = 2$，我们第一次询问了 $1,2$ 这两个位置的 01 数量乘积，发现为 $1$，我们第一次猜测最终字符串为 00，发现猜错了；我们第二次猜测最终字符串为 01，发现猜对了。

对于第三组测试数据，$n = 8$，我们第一次询问了 $1,3,8$ 这三个位置的 01 数量乘积，发现为 $0$，我们第一次猜测最终字符串为 10100001，发现猜对了。

设你在所有测试点的所有测试数据中最大询问次数为 $x$，则：

$x > 1001$，则你会获得 $0$ 分。
$x = 1001$，则你会获得 $5$ 分。
$385 \le x \le 1000$，则你会获得 $5 + 90 \times \biggl(1 - \displaystyle\frac{x-385}{1001-385}\biggr)$ 分。
$x \le 384$，则你会获得 $100$ 分。

本题采用捆绑测试。

对于所有数据，保证 $1 \le T \le 10$，$1 \le n \le 1000$。