A. Джонни и древний компьютер
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Джонни обнаружил древний сломанный компьютер. У него есть только один регистр, в который можно записать некоторое значение. После чего, за одну операцию вы можете применить к значению битовый сдвиг влево или вправо на не более чем три позиции. Сдвиг вправо запрещен, если в результате будут потеряны единичные биты. Так что, на самом деле, за одну операцию вы можете умножить или разделить значение на $$$2$$$, $$$4$$$ или $$$8$$$, и деление разрешено только если значение делится нацело на выбранный делитель.

Формально, если регистр содержит целое положительное число $$$x$$$, за одну операцию оно может быть заменено одним из следующих:

  • $$$x \cdot 2$$$
  • $$$x \cdot 4$$$
  • $$$x \cdot 8$$$
  • $$$x / 2$$$, если $$$x$$$ делится на $$$2$$$
  • $$$x / 4$$$, если $$$x$$$ делится на $$$4$$$
  • $$$x / 8$$$, если $$$x$$$ делится на $$$8$$$

Например, если $$$x = 6$$$, за одну операцию оно может быть заменено на $$$12$$$, $$$24$$$, $$$48$$$ или $$$3$$$. Значение $$$6$$$ не делится на $$$4$$$ или $$$8$$$, поэтому существуют только четыре варианта замены.

Теперь Джонни интересуется, какое минимальное количество операций необходимо, если он запишет в регистр значение $$$a$$$ и в конце хочет получить там значение $$$b$$$.

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

Входные данные состоят из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Следующие $$$t$$$ строк содержат описание наборов входных данных.

Первая и единственная строка каждого набора входных данных содержит целые числа $$$a$$$ и $$$b$$$ ($$$1 \leq a, b \leq 10^{18}$$$) — исходное значение и желаемое итоговое значение, соответственно.

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

Выведите $$$t$$$ строк, каждая строка должна содержать одно целое число, обозначающее минимальное количество операций, которое Джонни должен выполнить. Если Джонни не сможет получить значение $$$b$$$ в конце, выведите $$$-1$$$.

Пример
Входные данные
10
10 5
11 44
17 21
1 1
96 3
2 128
1001 1100611139403776
1000000000000000000 1000000000000000000
7 1
10 8
Выходные данные
1
1
-1
0
2
2
14
0
-1
-1
Примечание

В первом наборе входных данных, Джонни может получить $$$5$$$ из $$$10$$$ сделав один сдвиг вправо на один (т.е. поделив на $$$2$$$).

Во втором наборе входных данных, Джонни может получить $$$44$$$ из $$$11$$$ сделав один сдвиг влево на два (т.е. умножив на $$$4$$$).

В третьем наборе входных данных, Джонни не может получить значение $$$21$$$ из значения $$$17$$$.

В четвертом наборе входных данных, исходное и желаемое значения совпадают, поэтому Джонни придется сделать $$$0$$$ операций.

В пятом наборе входных данных, Джонни может получить $$$3$$$ из $$$96$$$ сделав два сдвига вправо: один на $$$2$$$, и другой на $$$3$$$ (т.е. поделив на $$$4$$$ и $$$8$$$).