두 배 또는 NOT

시작점인 음이 아닌 정수 $\mathbf{S}$와 끝점인 음이 아닌 정수 $\mathbf{E}$가 주어진다. $\mathbf{S}$와 $\mathbf{E}$는 모두 이진 표현으로 주어진다(즉, 밑이 $2$인 표기법으로 쓰여 주어진다). 목표는 $\mathbf{S}$를 $\mathbf{E}$로 변환하는 것이다. 다음 두 연산을 사용할 수 있다:

• 현재 값을 두 배로 만든다.

• 현재 값에 비트 단위 NOT을 취한다. 현재 값의 이진 표현은 불필요한 선행 영 없이 사용하며, 연산으로 생긴 불필요한 선행 영은 제거한다. (필요한 유일한 선행 영은 $0$의 표현에 있는 영이다.)

예를 들어, 두 배 연산을 사용하면 $6$는 $12$가 되고, $0$는 $0$가 되며, $10$는 $20$가 된다. NOT 연산을 사용하면 $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$인 정수를 뜻한다.)

이 연산들을 원하는 만큼 어떤 순서로든 사용할 수 있다. 예를 들어, 먼저 NOT 연산을 사용하고, 이어서 두 배 연산을 두 번 사용한 다음, 다시 NOT 연산을 사용하여 $\mathbf{S} = 10001_2$을 $\mathbf{E} = 111_2$로 변환할 수 있다: $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.$

변환을 완료하는 데 필요한 최소 연산 횟수를 구하거나, 불가능하다고 답한다.

제한

시간 제한: 10초. 메모리 제한: 1 GB. $1 \le \mathbf{T} \le 100$. $\mathbf{S}$의 각 문자는 0 또는 1이다. $\mathbf{S}$의 첫 자릿수는 $\mathbf{S}$의 길이가 $1$일 때만 0일 수 있다. $\mathbf{E}$의 각 문자는 0 또는 1이다. $\mathbf{E}$의 첫 자릿수는 $\mathbf{E}$의 길이가 $1$일 때만 0일 수 있다.

테스트 세트 1 (결과 공개)

$\mathbf{S} \le 8$의 길이는 $1 \le$. $\mathbf{E} \le 8$의 길이는 $1 \le$.

테스트 세트 2 (결과 비공개)

$\mathbf{S} \le 100$의 길이는 $1 \le$. $\mathbf{E} \le 100$의 길이는 $1 \le$.

입력의 첫 줄에는 테스트 케이스의 수 $\mathbf{T}$가 주어진다. 이어서 $\mathbf{T}$개의 테스트 케이스가 주어진다. 각 테스트 케이스는 한 줄로 이루어지며, 시작 정수와 끝 정수의 이진 표현인 두 문자열 $\mathbf{S}$와 $\mathbf{E}$가 각각 주어진다.

각 테스트 케이스마다 Case #$x$: $y$를 포함하는 한 줄을 출력한다. 여기서 $x$는 테스트 케이스 번호이며(1부터 시작), 두 연산을 사용하여 $\mathbf{S}$를 $\mathbf{E}$로 변환할 방법이 없다면 $y$은 IMPOSSIBLE이다. 그렇지 않다면 $y$는 $\mathbf{S}$를 $\mathbf{E}$로 변환하는 데 필요한 최소 연산 횟수이다.

예제 케이스 #1은 문제 본문에 제시된 예시이다.

예제 케이스 #2, #3, #4을 각각 해결하는 가능한 최적의 방법은 다음과 같다: $1011_2 \overset{\text{NOT}}{\Longrightarrow} 100_2 \overset{\times 2}{\Longrightarrow} 1000_2 \overset{\text{NOT}}{\Longrightarrow} 111_2,$ $1010_2 \overset{\times 2}{\Longrightarrow} 10100_2 \overset{\text{NOT}}{\Longrightarrow} 1011_2, \text{ and}$ $0_2 \overset{\text{NOT}}{\Longrightarrow} 1_2.$

예제 케이스 #5에서는 어떤 연산 순서를 사용해도 $0_2$에서 $101_2$으로 갈 수 없다.

예제 케이스 #6에서는 $\mathbf{S} = \mathbf{E}$이므로 어떤 연산도 수행할 필요가 없다.