P13381 [GCJ 2011 #3] Mystery Square

我写下了一个很大的完全平方数的二进制表示，然后把其中一些数字替换成了问号。你能找出我原来的数字是什么吗？

输入的第一行是测试用例的数量 $T$。接下来的 $T$ 行，每行包含一个字符串 $S$，表示一个完全平方数的二进制表示，但其中一些数字被问号替换了。

对于每个测试用例，输出一行，格式为 "Case #$x$: $N$"，其中 $x$ 是测试用例编号（从 1 开始），$N$ 是将 $S$ 中每个 '?' 替换为 '0' 或 '1' 后得到的完全平方数的二进制表示。

**限制条件** - $1 \leq T \leq 25$。 - $S$ 以 '1' 开头。 - $S$ 只包含字符 '0'、'1' 和 '?'。 - 每个测试用例都恰好有一种可能的 $N$。 **小数据集（10 分，测试集 1 - 可见）** - $S$ 最多 $60$ 个字符。 - $S$ 中最多有 $20$ 个 '?' 字符。 - 时间限制：6 秒。 **大数据集（31 分，测试集 2 - 隐藏）** - $S$ 最多 $125$ 个字符。 - $S$ 中最多有 $40$ 个 '?' 字符。 - 时间限制：20 秒。 由 ChatGPT 4.1 翻译