← 返回题目列表

Codeforces · 2184/C

C. 巨大的一堆

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

安德烈有一大堆 $$$n$$$ 苹果。他可以将这堆分成两个较小的堆:如果堆中有 $$$x$$$ 苹果,他将得到带有 $$$\lfloor \frac{x}{2} \rfloor$$$$$$^{\text{∗}}$$$ 和 $$$\lceil \frac{x}{2} \rceil$$$$$$^{\text{†}}$$$ 苹果的堆。这个分区需要 Andrei $$$1$$$ 分钟。

Andrei 想吃 $$$k$$$ 个苹果,但他根本不想数。这就是为什么他想要获得一堆恰好包含 $$$k$$$ 个苹果的原因。确定是否可以通过进行桩分割来实现这一点。如果可能的话,找出安德烈获得一堆恰好有 $$$k$$$ 个苹果的最短可能时间。

$$$^{\text{*}}$$$$$$\lfloor \frac{x}{2} \rfloor$$$ — 最大整数 $$$\le \frac{x}{2}$$$。

$$$^{\text{†}}$$$$$$\lceil \frac{x}{2} \rceil$$$ — 最小整数 $$$\ge \frac{x}{2}$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ $$$(1 \le t \le 10^4)$$$ — 测试用例的数量。以下几行描述了测试用例。

在每个测试用例的唯一一行中,给出了两个整数 $$$n$$$ 和 $$$k$$$——一大堆苹果的数量和 Andrei 想要在一堆中获得的苹果数量 $$$(1 \le n, k \le 10^9)$$$。

输出

对于每个测试用例,如果不可能获得一堆恰好包含 $$$k$$$ 个苹果,则输出 $$$-1$$$。否则,输出获得这样一堆所需的最短可能时间。

示例

输入
复制

4
10 3
11 5
21 4
1000000000 1

输出
复制

2
1
-1
29

注意

在第一个测试用例中,第一次划分后,将创建两堆 $$$5$$$ 苹果。如果其中一个被分开,就会得到一堆 $$$2$$$ 和 $$$3$$$ 苹果,所以答案是 $$$2$$$。

在第二个测试用例中,如果将一堆苹果分成两堆,则会导致一堆有 $$$5$$$ 和 $$$6$$$ 苹果,所以答案是 $$$1$$$。

在第三个测试用例中,只能获得包含 $$$1$$$、$$$2$$$、$$$3$$$、$$$5$$$、$$$6$$$、$$$10$$$、$$$11$$$ 或 $$$21$$$ 苹果的堆,因此答案为 $$$-1$$$。