← 返回题目列表

Codeforces · 1875/C

C. 水母和青苹果

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

水母有 $$$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}$$$。