水母有 $$$n$$$ 青苹果块。每片青苹果重$$$1~\text{kg}$$$。 Jellyfish 希望将这些青苹果片平均分配给 $$$m$$$ 人。
水母有一把神刀。水母每次可以选择一块青苹果,并将其分成两块较小的苹果,每块的重量是原苹果的一半。
Jellyfish 想知道最少需要多少次操作才能将青苹果块分开,从而使每个人收到的苹果块的总重量相同。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行也是唯一一行包含两个整数,$$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 10^9$$$) - 最初的青苹果块数和人数。
输出
对于每个测试用例,输出一个整数 - 将所有青苹果平均分配给 $$$m$$$ 人所需的最少操作数。如果使用有限数量的操作无法实现这一点,则输出 $$$-1$$$ 代替。
示例
输入 #1
4 10 5 1 5 10 4 3 4
输出 #1
0 -1 2 5
注意
在第一个测试用例中,我们不需要划分苹果块。每人将收到$$$2$$$个$$$1~\text{kg}$$$,每人收到的苹果块总重量为$$$2~\text{kg}$$$。
在第二个测试用例中,不可能使用有限次数的操作将苹果均分。
在第三个测试用例中,我们可以将两个重量为 $$$1~\text{kg}$$$ 的苹果分开,得到 $$$4$$$ 重量为 $$$0.5~\text{kg}$$$ 的苹果。每人将收到 $$$1$$$ 重 $$$0.5~\text{kg}$$$ 的苹果和 $$$2$$$ 重 $$$1~\text{kg}$$$ 的苹果。每人收到的苹果块总重量为$$$2.5~\text{kg}$$$。
在第四个测试用例中,我们首先将所有 $$$3$$$ 重量 $$$1~\text{kg}$$$ 的苹果块相除,得到 $$$6$$$ 重量 $$$0.5~\text{kg}$$$ 的苹果块。然后,我们再将两块重量为$$$0.5~\text{kg}$$$的苹果分开,得到$$$4$$$块重量为$$$0.25~\text{kg}$$$的苹果。每人将获得 $$$1$$$ 重 $$$0.5~\text{kg}$$$ 的苹果和 $$$1$$$ 重 $$$0.25~\text{kg}$$$ 的苹果。每人收到的苹果总重量为$$$0.75~\text{kg}$$$。