22898번 - Double or NOTing 서브태스크다국어

문제

You are given a starting non-negative integer $S$ and an ending non-negative integer $E$. Both $S$ and $E$ are given by their binary representation (that is, they are given written in base 2ドル$). Your goal is to transform $S$ into $E$. The following two operations are available to you:

• Double your current value.
• Take the bitwise NOT of your current value. The binary representation of your current value is taken without unnecessary leading zeroes, and any unnecessary leading zeroes produced by the operation are dropped. (The only necessary leading zero is the one in the representation of 0ドル$).

For example, by using the double operation, 6ドル$ becomes 12ドル,ドル 0ドル$ becomes 0ドル,ドル and 10ドル$ becomes 20ドル$. By using the NOT operation, 0ドル$ becomes 1ドル,ドル 1ドル$ becomes 0ドル,ドル 3ドル=11_2$ becomes 0ドル,ドル 14ドル=1110_2$ becomes 1ドル,ドル 10ドル=1010_2$ becomes 5ドル=101_2,ドル and 5ドル=101_2$ becomes 2ドル=10_2$. ($X_2$ means the integer whose binary representation is $X$).

You can use these operations as many times as you want in any order. For example, you can transform $S=10001_2$ to $E=111_2$ using the NOT operation first, then using the double operation twice, and then another NOT operation:

$10001ドル_2 \overset{\text{NOT}}{\Longrightarrow} 1110_2 \overset{\times 2}{\Longrightarrow} 11100_2 \overset{\times 2}{\Longrightarrow} 111000_2 \overset{\text{NOT}}{\Longrightarrow}111_2\text{.}$$

Determine the smallest number of operations needed to complete the transformation, or say it is impossible to do so.

입력

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each consists of a single line containing two strings $S$ and $E,ドル the binary representations of the starting and ending integers, respectively.

출력

For each test case, output one line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is IMPOSSIBLE if there is no way to transform $S$ into $E$ using the two operations. Otherwise, $y$ is the smallest number of operations needed to transform $S$ into $E$.

제한

• 1ドル \le T \le 100$.
• Each character of $S$ is either 0 or 1.
• The first digit of $S$ can be 0 only if the length of $S$ is 1ドル$.
• Each character of $E$ is either 0 or 1.
• The first digit of $E$ can be 0 only if the length of $E$ is 1ドル$.

Test Set 1 (14점)

• 1 ≤ the length of $S$ ≤ 8.
• 1 ≤ the length of $E$ ≤ 8.

Test Set 2 (26점)

• 1 ≤ the length of $S$ ≤ 100.
• 1 ≤ the length of $E$ ≤ 100.

힌트

Sample Case #1 is the example shown in the main part of the statement.

These are possible optimal ways of solving Sample Cases #2, #3, and #4, respectively:

$1011ドル_2 \overset{\text{NOT}}{\Longrightarrow} 100_2 \overset{\times 2}{\Longrightarrow} 1000_2 \overset{\text{NOT}}{\Longrightarrow}111_2\text{,}$$

$1010ドル_2 \overset{\times 2}{\Longrightarrow} 10100_2 \overset{\text{NOT}}{\Longrightarrow} 1011_2\text{, and}$$

$0ドル_2 \overset{\text{NOT}}{\Longrightarrow} 1_2\text{.}$$

In Sample Case #5, it is not possible to get from 0ドル_2$ to 101ドル_2$ with any sequence of operations.

In Sample Case #6, we do not need to perform any operations because $S=E$.