题目描述

给定一个起始非负整数 $\textbf{S}$ 和一个目标非负整数 $\textbf{E}$。$\textbf{S}$ 和 $\textbf{E}$ 都以二进制形式给出（即以 2 为基数的表示）。你的目标是通过以下两种操作将 $\textbf{S}$ 转换为 $\textbf{E}$：

1. 双倍操作：将当前值乘以 2。
2. 取反操作：对当前值进行按位取反。当前值的二进制表示不包含不必要的前导零，且操作后产生的不必要前导零将被移除。（唯一必要的前导零是表示 0 时的那个零）。

例如：

• 双倍操作：6 变为 12，0 保持为 0，10 变为 20。
• 取反操作：0 变为 1，1 变为 0，$3 = 11_2$ 变为 0，$14 = 1110_2$ 变为 1，$10 = 1010_2$ 变为 $5 = 101_2$，$5 = 101_2$ 变为 $2 = 10_2$。（$X_2$ 表示二进制表示为 $X$ 的整数）。

你可以按任意顺序、任意次数使用这两种操作。例如，可以通过先取反，再两次双倍，最后再取反，将 $\textbf{S} = 10001_2$ 转换为 $\textbf{E} = 111_2$：

$$10001_2 \xrightarrow{\text{取反}} 1110_2 \xrightarrow{\times2} 11100_2 \xrightarrow{\times2} 111000_2 \xrightarrow{\text{取反}} 111_2. $$

你的任务是确定完成转换所需的最少操作次数，或者判定转换不可能。

输入格式

输入的第一行是测试用例的数量 $\textbf{T}$。接下来是 $\textbf{T}$ 个测试用例，每个测试用例占一行，包含两个字符串 $\textbf{S}$ 和 $\textbf{E}$，分别表示起始整数和目标整数的二进制形式。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 IMPOSSIBLE（如果无法通过操作将 $\textbf{S}$ 转换为 $\textbf{E}$），否则 $y$ 是所需的最少操作次数。

输入输出样例 #1

输入 #1

6
10001 111
1011 111
1010 1011
0 1
0 101
1101011 1101011

输出 #1

Case #1: 4
Case #2: 3
Case #3: 2
Case #4: 1
Case #5: IMPOSSIBLE
Case #6: 0

说明/提示

样例解释

样例 #1 是题目描述中给出的示例。

以下是样例 #2、#3 和 #4 的可能最优解法：

$$1011_2 \xrightarrow{\text{取反}} 100_2 \xrightarrow{\times2} 1000_2 \xrightarrow{\text{取反}} 111_2, $$$$1010_2 \xrightarrow{\times2} 10100_2 \xrightarrow{\text{取反}} 1011_2, $$$$0_2 \xrightarrow{\text{取反}} 1_2.$$

在样例 #5 中，无法通过任何操作序列将 $0_2$ 转换为 $101_2$。

在样例 #6 中，$\textbf{S} = \textbf{E}$，因此无需任何操作。

数据范围

• $1 \leq \textbf{T} \leq 100$。
• $\textbf{S}$ 的每个字符是 0 或 1。
• $\textbf{S}$ 的首字符可以是 0，仅当 $\textbf{S}$ 的长度为 1 时。
• $\textbf{E}$ 的每个字符是 0 或 1。
• $\textbf{E}$ 的首字符可以是 0，仅当 $\textbf{E}$ 的长度为 1 时。

测试集 1（14 分，可见判定）

• $1 \leq \text{\textbf{S} 的长度} \leq 8$。
• $1 \leq \text{\textbf{E} 的长度} \leq 8$。

测试集 2（26 分，隐藏判定）

• $1 \leq \text{\textbf{S} 的长度} \leq 100$。
• $1 \leq \text{\textbf{E} 的长度} \leq 100$。

翻译由 DeepSeek V3 完成