시간 제한메모리 제한제출정답맞힌 사람정답 비율
20 초 (추가 시간 없음) 1024 MB222113100.000%

문제

Przypomnijmy jak wygląda drzewo binarne. Węzły tego drzewa będziemy numerowali kolejnymi liczbami naturalnymi od 1, idąc kolejnymi poziomami od góry do dołu poczynając od korzenia (wierzchołka na samej górze), a na każdym poziomie od lewej do prawej:

Drzewo binarne narysowane do węzła nr 18. Zwróć uwagę, że drzewo ma więcej niż 18 węzłów.

W tym zadaniu będziemy rozpatrywali najkrótsze ścieżki pomiędzy dwoma węzłami. Przykładowo, najkrótsza ścieżka między węzłami numer 8 oraz 5 ma trzy krawędzie i przebiega przez węzły 4 oraz 2.

Napisz program, który wczyta zapytania dotyczące ścieżek pomiędzy dwoma węzłami drzewa, dla każdego z nich wyznaczy długość najkrótszej ścieżki między tymi węzłami i wypisze wyniki na standardowe wyjście.

입력

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q (1 ≤ Q ≤ 100 000), określająca liczbę zapytań. W kolejnych Q wierszach znajdują się zapytania, po jednym w wierszu. Opis każdego zapytania składa się z dwóch liczb naturalnych Ai oraz Bi (1 ≤ Ai, Bi ≤ 1018), oddzielonych pojedynczym odstępem i określających numery węzłów, dla których należy wyznaczyć ścieżkę.

출력

Twój program powinien wypisać na wyjście Q wierszy. W i-tym z nich powinna się znaleźć liczba całkowita – liczba krawędzi, które należy pokonać, aby przedostać się w drzewie z węzła o numerze Ai do węzła Bi.

예제 입력 1

3
8 5
6 7
4 1

예제 출력 1

3
2
2

예제 입력 2

1
1 1000

예제 출력 2

9

예제 입력 3

4
10 20
20 10
10 1
1 10

예제 출력 3

1
1
3
3

예제 입력 4

1
1000000000 5000000000

예제 출력 4

61