Недавно Джонни обнаружил древний сломанный компьютер. У него есть только один регистр, в который можно записать некоторое значение. После чего, за одну операцию вы можете применить к значению битовый сдвиг влево или вправо на не более чем три позиции. Сдвиг вправо запрещен, если в результате будут потеряны единичные биты. Так что, на самом деле, за одну операцию вы можете умножить или разделить значение на \(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\) строк, каждая строка должна содержать одно целое число, обозначающее минимальное количество операций, которое Джонни должен выполнить. Если Джонни не сможет получить значение \(b\) в конце, выведите \(-1\).
Примечание
В первом наборе входных данных, Джонни может получить \(5\) из \(10\) сделав один сдвиг вправо на один (т.е. поделив на \(2\)).
Во втором наборе входных данных, Джонни может получить \(44\) из \(11\) сделав один сдвиг влево на два (т.е. умножив на \(4\)).
В третьем наборе входных данных, Джонни не может получить значение \(21\) из значения \(17\).
В четвертом наборе входных данных, исходное и желаемое значения совпадают, поэтому Джонни придется сделать \(0\) операций.
В пятом наборе входных данных, Джонни может получить \(3\) из \(96\) сделав два сдвига вправо: один на \(2\), и другой на \(3\) (т.е. поделив на \(4\) и \(8\)).
Примеры
| № | Входные данные | Выходные данные |
|
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
|