Жители этого мира живут в городе с бесконечным количеством домов, где каждый дом имеет уникальный номер $n$, являющийся положительным целым числом. Улицы в этом городе устроены следующим образом: для каждого дома $n$ существует только одна дорога, ведущая к дому с бо́льшим номером, а именно к $n + \mathrm{lowbit}(n)$.

Функция $\mathrm{lowbit}(n)$ определяется как значение, полученное при сохранении в двоичном представлении числа $n$ только младшего значащего бита. Существует удобный способ вычисления этой функции с помощью побитовых операций: lowbit(n) = n & -n.

Можно доказать, что любые два дома достижимы друг из друга по этим двусторонним дорогам. Ваша задача — обработать несколько запросов и вычислить длину кратчайшего пути между двумя домами, где прохождение по каждому ребру считается за одну единицу длины.

Входные данные

Первая строка содержит целое число $q$ — количество запросов.

Далее следуют $q$ строк, каждая из которых содержит два положительных целых числа $x$ и $y$, обозначающих номера двух домов.

Выходные данные

Выведите $q$ строк, в каждой из которых должно быть записано одно целое число — длина кратчайшего пути.

Примеры

Пример 1

2
1 3
2 4

Пример 1

3
1

Подзадачи

Для $20\%$ данных гарантируется, что $1 \leq q \leq 10$, $1 \le x,y \le 2^{3}$.

Для $30\%$ данных гарантируется, что $1 \leq q \leq 500$, $1 \le x,y \le 2^{9}$.

Для $70\%$ данных гарантируется, что $1 \leq q \leq 10^5$, $1 \le x,y \le 2^{20}$.

Для $100\%$ данных гарантируется, что $1 \leq q \leq 3 \times 10^5$, $1 \le x, y \le 2^{60}$.