Mystery Square

#### Round 3, 2011

Submit Solution(Code Jam Page)

### Problem

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?

### Input

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

### Output

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

### Limits

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

#### Small dataset

S is at most 60 characters long.
S contains at most 20 '?' characters.

#### Large dataset

S is at most 125 characters long.
S contains at most 40 '?' characters.

### Sample

 Input Output ``` 3 1??? 1 10??110??00??1000??``` ``` Case #1: 1001 Case #2: 1 Case #3: 1011110110000100001```

Points Correct Attempted
10pt 317 342
31pt 1 46