수수께끼의 제곱수

나는 이진수로 된 큰 완전제곱수를 적은 다음, 일부 자릿수를 물음표로 바꾸었다. 원래 수가 무엇이었는지 알아낼 수 있는가?

제한

1 ≤ T ≤ 25. S는 '1'로 시작한다. S에는 문자 '0', '1', '?'만 포함된다. 모든 테스트 케이스에서 N으로 가능한 선택지는 정확히 하나이다. 메모리 제한: 1GB.

작은 데이터셋 (테스트 세트 1 - 공개)

S의 길이는 최대 60자이다. S에는 '?' 문자가 최대 20개 포함된다. 시간 제한: 30초.

큰 데이터셋 (테스트 세트 2 - 비공개)

S의 길이는 최대 125자이다. S에는 '?' 문자가 최대 40개 포함된다. 시간 제한: 60초.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 한 줄에 하나씩 주어진다. 각 줄에는 일부 자릿수가 물음표로 대체된, 이진수로 쓰인 완전제곱수 S가 주어진다.

각 테스트 케이스마다 "Case #x: N"을 포함하는 한 줄을 출력한다. 여기서 x는 케이스 번호이며(1부터 시작), N은 S의 각 '?' 문자를 '0' 문자 또는 '1' 문자로 대체하여 얻은, 이진수로 쓰인 완전제곱수이다.