미스터리 제곱수 (스몰)

큰 완전제곱수를 2진법으로 적은 다음, 몇몇 자리의 숫자를 물음표로 바꿨다. 원래 수가 무엇이었는지 알아내자.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어지는 $T$개의 줄에 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄에는 문자열 $S$가 주어지며, $S$는 완전제곱수를 2진법으로 적은 뒤 일부 자리를 물음표로 바꾼 것이다.

각 테스트 케이스마다 Case #x: N 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, N은 $S$의 물음표를 각각 '0' 또는 '1'로 바꿔서 얻은 완전제곱수를 2진법으로 적은 것이다.

• $1 \le T \le 25$
• $S$는 '1'로 시작한다.
• $S$는 '0', '1', '?' 세 가지 문자만 포함한다.
• 모든 테스트 케이스에서 N으로 가능한 값은 정확히 하나이다.
• $S$의 길이는 60 이하이다.
• $S$에 들어 있는 '?'는 20개 이하이다.