CF2013C Password Cracking

迪马什得知曼苏尔向朋友泄露了一些关于他的不愉快言论，于是他决心揭开曼苏尔的密码，看看具体内容是什么。 曼苏尔对自己的密码充满信心，他表示自己的密码是一个长度为 $ n $ 的二进制字符串。同时，他愿意回答迪马什的问题： 迪马什可以给出一个二进制字符串 $ t $ ，曼苏尔则回答 $ t $ 是否是他的密码的一个子串（即一段连续的字符序列）。 请帮助迪马什在不超过 $ 2n $ 次询问内猜出密码；否则，曼苏尔将识破伎俩并停止与他交流。

输入包含多个测试用例。第一行包含一个整数 $ t $ ，表示测试用例的数量（$ 1 \le t \le 100 $）。接下来描述每个测试用例。

每个测试用例一开始，读取一个整数 $ n $ ，表示二进制字符串的长度（$ 1 \le n \le 100 $）。然后开始猜测这个字符串。 在猜测字符串 $ s $ 的过程中，你可以进行不超过 $ 2n $ 次以下类型的查询： - "? $ t $"，其中 $ t $ 是满足 $ 1 \le |t| \le n $ 的二进制字符串。 对于每次查询，你将收到一个结果：如果 $ t $ 是 $ s $ 的子串，返回 $ 1 $；否则返回 $ 0 $。 一旦确认了密码字符串 $ s $，输出格式如下： - "! $ s $"，其中 $ s $ 是长度为 $ n $ 的二进制字符串。 完成一个测试用例后，继续下一个测试用例的解答。 如果在过程中发生错误尝试或超过 $ 2n $ 次查询限制，将收到 $ -1 $ 作为回应，并被判定为“错误答案”。此时程序应立即终止，以避免未定义的结果。 记得在输出查询结果之后，添加一个换行并刷新输出缓冲区，否则程序会被判定为“程序挂起”。常用的刷新缓冲方法如下： - C++ 中使用 `fflush(stdout)` 或 `cout.flush()` - Java 中使用 `System.out.flush()` - Pascal 中使用 `flush(output)` - Python 中使用 `sys.stdout.flush()` - 其他语言请参考相关文档进行操作。 ### 数据范围与提示 举例说明：对于字符串 $ 010 $ ，查询的结果是： - "? 00"——因为 $ 00 $ 不是 $ 010 $ 的子串，所以结果是 $ 0 $。 - "? 000"——因为 $ 000 $ 不是子串，结果是 $ 0 $。 - "? 010"——因为 $ 010 $ 是子串，结果是 $ 1 $。 在以下示例中，字符串分别为 $ 1100 $ 、 $ 0110 $ 和 $ 10 $。 **本翻译由 AI 自动生成**

In the first example, the string $ 010 $ is given. Therefore, the answers to the queries are as follows: "? 00" $ 00 $ is not a substring of $ 010 $ , so the answer is $ 0 $ . "? 000" $ 000 $ is not a substring, so the answer is $ 0 $ . "? 010" $ 010 $ is a substring, so the answer is $ 1 $ . In the second example, the string is $ 1100 $ , in the third $ 0110 $ , and in the fourth $ 10 $ .