Mystery Square (Large)

Fill each ? in the binary string with 0 or 1 so the result is the binary form of a perfect square.

Hard8Number theoryBacktrackingBit manipulationNo attempts yetTime limit60sMemory limit512 MB

Description

Examples1

Problem

Someone wrote a perfect square in binary and then covered some of its digits with '?'. Given the covered string S, recover the original number. Every digit that is not '?' stays as it is, and each '?' becomes '0' or '1' so that the whole string is the binary representation of a perfect square. The length does not change, so you cannot prepend a leading zero.

Input

The first line contains the number of test cases, T. Each of the next T lines contains one string S: a perfect square written in binary, with some of its digits replaced by '?'.

Output

For each test case, print one line of the form Case #x: N, where x is the test case number starting from 1 and N is the binary representation of a perfect square obtained by replacing each '?' in S with '0' or '1'.

Constraints

$1 \le T \le 25$
The first character of S is '1'.
S consists only of the characters '0', '1', and '?'.
In every test case exactly one N is possible.
The length of S is at most 125.
S contains at most 40 '?' characters.