Mieszkańcy tego świata żyją w mieście z nieskończoną liczbą domów. Każde miejsce zamieszkania ma unikalny numer $n$, będący liczbą całkowitą dodatnią. Ulice w tym mieście są skonstruowane w następujący sposób: dla każdego domu $n$ istnieje tylko jedna ulica prowadząca do domu o numerze większym niż $n$, a mianowicie do $n + \mathrm{lowbit}(n)$.

Funkcja $\mathrm{lowbit}(n)$ jest zdefiniowana jako wartość uzyskana przez pozostawienie w zapisie binarnym liczby $n$ tylko najmniej znaczącego bitu ustawionego na 1. Istnieje bardzo wygodny sposób obliczenia tej wartości za pomocą operacji bitowych: lowbit(n) = n & -n.

Można udowodnić, że między dowolnymi dwoma domami można się przemieszczać w obie strony za pomocą tych dróg. Twoim zadaniem jest obsłużenie kilku zapytań, polegających na obliczeniu długości najkrótszej ścieżki między dwoma domami, przy założeniu, że przejście każdą krawędzią ma długość jednostkową.

Wejście

Pierwsza linia zawiera liczbę całkowitą $q$, oznaczającą liczbę zapytań.

Każda z kolejnych $q$ linii zawiera dwie liczby całkowite dodatnie $x$ oraz $y$, oznaczające numery dwóch domów.

Wyjście

Dla każdego zapytania wypisz w osobnej linii jedną liczbę całkowitą oznaczającą długość najkrótszej ścieżki.

Przykład

Przykład 1

Wejście

2
1 3
2 4

Wyjście

3
1

Podzadania

Dla $20\%$ danych wejściowych: $1 \leq q \leq 10$, $1 \le x,y \le 2^{3}$.

Dla $30\%$ danych wejściowych: $1 \leq q \leq 500$, $1 \le x,y \le 2^{9}$.

Dla $70\%$ danych wejściowych: $1 \leq q \leq 10^5$, $1 \le x,y \le 2^{20}$.

Dla $100\%$ danych wejściowych: $1 \leq q \leq 3 \times 10^5$, $1 \le x, y \le 2^{60}$.