시간 제한메모리 제한제출정답맞힌 사람정답 비율
60 초 512 MB324330.000%

## 문제

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, TT 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.

## 출력

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.

## 제한

• 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.
• S is at most 125 characters long.
• S contains at most 40 '?' characters.

## 예제 입력 1

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


## 예제 출력 1

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


## 채점 및 기타 정보

• 예제는 채점하지 않는다.