Mystery Square
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

Subscribe to our newsletter

Join our monthly newsletter and never miss out on new stories and promotions.