题目描述

Johnny 最近发现了一台古老且损坏的计算机。这台机器只有一个寄存器，只能存放一个变量。每次操作时，你可以将寄存器中的数的二进制位向左或向右移动最多三位。右移操作如果会截断某些 $1$，则不允许进行。因此，实际上每次操作你可以将当前数乘以 $2$、$4$ 或 $8$，或者在当前数能被选定的除数整除时，将其除以 $2$、$4$ 或 $8$。

具体来说，如果寄存器中存放着正整数 $x$，一次操作后它可以被替换为以下之一：

• $x \times 2$
• $x \times 4$
• $x \times 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 需要执行的最少操作次数。如果无法得到 $b$，则输出 $-1$。

说明/提示

在第一个测试用例中，Johnny 可以通过右移一位（即除以 $2$）将 $10$ 变为 $5$。

在第二个测试用例中，Johnny 可以通过左移两位（即乘以 $4$）将 $11$ 变为 $44$。

在第三个测试用例中，Johnny 无法将 $17$ 变为 $21$。

在第四个测试用例中，初始值和目标值相等，所以 Johnny 需要 $0$ 次操作。

在第五个测试用例中，Johnny 可以通过两次右移：先右移两位（除以 $4$），再右移三位（除以 $8$），将 $96$ 变为 $3$。

由 ChatGPT 4.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