미스터리 제곱수 (Large)

완전제곱수 하나를 이진법으로 적은 뒤 몇 개의 자리를 '?'로 가렸다. 가려진 문자열 S가 주어지면 원래 수를 복원하라. '?'가 아닌 자리는 그대로 두고, 각 '?'를 '0' 또는 '1'로 바꿔서 어떤 완전제곱수의 이진 표현이 되도록 만들면 된다. 문자열의 길이는 그대로이므로 맨 앞에 0을 덧붙일 수 없다.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 다음 T개의 줄에 문자열 S가 한 줄에 하나씩 주어진다. S는 완전제곱수를 이진법으로 적은 다음 일부 자리를 '?'로 바꾼 문자열이다.

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

• $1 \le T \le 25$
• S의 첫 글자는 '1'이다.
• S는 '0', '1', '?'로만 이루어져 있다.
• 모든 테스트 케이스에서 가능한 N은 정확히 하나이다.
• S의 길이는 125 이하이다.
• S에 들어 있는 '?'는 40개 이하이다.