이진 트리에서의 산책

면접 대비

시간 제한20초메모리 제한1024 MB

요약

레벨 순으로 번호가 매겨진 이진 트리에서 Q개의 질의마다 두 노드 A와 B 사이의 간선 수를 구합니다.

난이도: 보통10점 중 4점
유형: 트리, 수학
정답자: 아직 제출이 없습니다

문제

이진 트리의 구조를 떠올려 보자. 노드에는 1부터 시작하는 자연수 번호를 붙인다. 루트(가장 위에 있는 노드)부터 시작해 각 레벨을 위에서 아래로, 같은 레벨 안에서는 왼쪽에서 오른쪽으로 번호를 매긴다.

18번 노드까지 그린 이진 트리이다. 이 트리의 노드는 18개보다 많다.

이 문제에서는 두 노드 사이의 최단 경로를 다룬다. 예를 들어 8번 노드와 5번 노드 사이의 최단 경로는 간선이 3개이며, 4번 노드와 2번 노드를 지난다.

트리에 있는 두 노드 사이의 경로를 묻는 질의를 읽고, 각 질의마다 두 노드 사이 최단 경로의 길이를 구해 표준 출력에 쓰는 프로그램을 작성하라.

입력

첫 줄에 질의의 개수를 나타내는 자연수 Q가 주어진다 ( $1 \le Q \le 100\,000$ ). 이어서 Q개의 줄에 질의가 한 줄에 하나씩 주어진다. 각 질의는 두 자연수 $A_i$ , $B_i$ ( $1 \le A_i, B_i \le 10^{18}$ )로 이루어지며, 하나의 공백으로 구분된다. 두 수는 경로를 구할 두 노드의 번호이다.

출력

Q개의 줄을 출력한다. i번째 줄에는 트리에서 노드 $A_i$ 에서 노드 $B_i$ 까지 이동할 때 지나야 하는 간선의 수를 적는다.

예제3

예제 1
입력
```
3
8 5
6 7
4 1
```
예상 출력
```
3
2
2
```
예제 2
입력
```
1
1 1000
```
예상 출력
```
9
```
예제 3
입력
```
4
10 20
20 10
10 1
1 10
```
예상 출력
```
1
1
3
3
```