문제
정올국의 사람들은 모두 자신의 소울메이트를 찾고 싶어한다. 사람들의 성격은 정수 pi(1≤pi≤1018)로 설명된다. 같은 성격을 가진 두 명은 소울메이트다. 사람들은 2를 곱하거나 2로 나누거나(pi가 짝수인 경우) 1을 더하는 "변경 작업"을 통해 성격을 변경할 수 있다.
정올국의 왕 정올킹은 처음에 임의의 방식으로 사람들을 짝을 지어준다. 그는 한 쌍의 사람들을 소울메이트로 만들기 위해 얼마나 많은 변경 작업이 필요한지 궁금하다. 각 쌍에 대해 쌍의 첫 번째 사람이 두 번째 사람과 소울메이트가 되기 위해 수행해야 하는 최소 변경 작업 수를 출력하는 프로그램을 작성하시오.
입력
첫 번째 줄에는 사람들의 쌍의 수인 N(1≤N≤10)이 주어진다.
이어서 N 줄은 각 사람들의 쌍의 성격을 나타내는 두 개의 정수가 주어지는데, 첫 번째 숫자는 두 번째 숫자와 일치하도록 변경해야 하는 성격이다.
출력
각 쌍에 대해 첫 번째 사람의 성격이 두 번째 사람의 성격과 일치하도록 만드는 데 필요한 최소 작업 수를 N줄에 걸쳐 출력하시오.
예제1
입력
6
31 13
12 8
25 6
10 24
1 1
997 120
출력
8
3
8
3
0
20
첫 번째 테스트 케이스의 경우 최적의 변경 순서는 31⟹32⟹16⟹8⟹9⟹10⟹11⟹12⟹13입니다.
두 번째 테스트 케이스의 경우 최적의 변경 순서는 12⟹6⟹7⟹8입니다.
출처
USACO 2022 January Silver