← 返回题目列表

Codeforces · 1362/A

A. 约翰尼和古代计算机

中文机器翻译题面 查看原题

约翰尼最近发现了一台古老的、坏掉的电脑。机器只有一个寄存器,允许人们在其中放入一个变量。然后,在一次操作中,您最多可以将其位向左或向右移动三个位置。如果右移切断了某些部分,则禁止右移。因此,事实上,在一次运算中,您可以将数字乘以或除以 $$$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$$$ 整除,因此只有四种替换变体。

现在,Johnny 想知道如果他将 $$$a$$$ 放入寄存器并想在最后得到 $$$b$$$,他需要执行多少次操作。

输入

输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 1000$$$) — 测试用例的数量。以下 $$$t$$$ 行包含测试用例的描述。

每个测试用例中的第一行也是唯一一行包含整数 $$$a$$$ 和 $$$b$$$ ($$$1 \leq a, b \leq 10^{18}$$$) - 分别是变量的初始值和目标值。

输出

输出 $$$t$$$ 行,每一行应包含一个整数,表示 Johnny 需要执行的最少操作数。如果 Johnny 最后无法得到 $$$b$$$,则写 $$$-1$$$。

示例

输入 #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
-1
0
2
2
14
0
-1
-1

注意

在第一个测试用例中,Johnny 通过使用右移一位(即除以 $$$2$$$)可以从 $$$10$$$ 达到 $$$5$$$。

在第二个测试用例中,Johnny 通过使用左移两倍(即乘以 $$$4$$$)可以从 $$$11$$$ 到达 $$$44$$$。

在第三个测试用例中,Johnny 不可能从 $$$17$$$ 达到 $$$21$$$。

在第四个测试用例中,初始值和目标值相等,因此 Johnny 必须执行 $$$0$$$ 操作。

在第五个测试用例中,Johnny 通过两次右移可以从 $$$96$$$ 到达 $$$3$$$:一次向右移动 $$$2$$$,另一次向右移动 $$$3$$$(即除以 $$$4$$$ 和 $$$8$$$)。