Problem description

Drzewo binarne jakie jest każdy widzi. W naszym zadaniu rozważymy nieskończone, pełne drzewo binarne tzn. takie, w którym każdy węzeł ma dwoje synów. Węzły drzewa będziemy numerowali kolejnymi liczbami naturalnymi idąc kolejnymi poziomami poczynając od korzenia, a na każdym poziomie od lewej do prawej:

Przechodzenie po węzłach takiego drzewa jest łatwe, a przynajmniej powinno być…

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ść ścieżki prostej między tymi węzłami i wypisze wyniki na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna Q, 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 A_i oraz B_i, oddzielonych pojedynczym odstępem i określających numery węzłów, dla których należy wyznaczyć ścieżkę.

Wyjście

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 A_i do węzła B_i.

Ograniczenia

1 ≤ Q ≤ 100 000, 1 ≤ A_i, B_i ≤ 10¹⁸.

Przykład

3
2 6
6 7
4 1

3
2
2