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 自动生成