#213498. [GCJ 2011 #3] Mystery Square

I have written down a large perfect square in binary, and then replaced some of the digits with question marks. Can you figure out what my original number was?

The first line of the input gives the number of test cases, . test cases follow, one per line. Each line contains : a perfect square written in binary, but with some of the digits replaced by question marks.

For each test case, output one line containing "Case #: ", where is the case number (starting from 1) and is a perfect square written in binary, obtained by replacing each '?' character in with either a '0' character or a '1' character.

样例输入 1

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

样例输出 1

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

Limits

• .
• begins with '1'.
• contains only the characters '0', '1', and '?'.
• In every test case, there is exactly one possible choice for .

Small dataset (10 Pts, Test set 1 - Visible)

• is at most characters long.
• contains at most '?' characters.
• Time limit: 30 6 seconds.

Large dataset (31 Pts, Test set 2 - Hidden)

• is at most characters long.
• contains at most '?' characters.
• Time limit: 60 20 seconds.