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