Description

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

Input Format

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

Output Format

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

3
1???
1
10??110??00??1000??

Case #1: 1001
Case #2: 1
Case #3: 1011110110000100001

Hint

限制条件

• $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 翻译