C. Huge Pile

时间限制：1 秒
内存限制：256 兆字节

问题描述

安德烈有一个巨大的苹果堆，包含 $n$ 个苹果。他可以将这个堆分成两个较小的堆：如果一堆中有 $x$ 个苹果，他将得到分别有 $\lfloor\frac{x}{2}\rfloor$ 和 $\lceil\frac{x}{2}\rceil$ 个苹果的两堆。每次分割需要安德烈花费 1 分钟。

安德烈想吃 $k$ 个苹果，但他完全不想去数苹果。因此，他希望通过执行若干次分割，最终得到一个恰好包含 $k$ 个苹果的堆。请判断这是否可能。如果可能，找出安德烈得到一个恰好包含 $k$ 个苹果的堆所需的最短时间。

$\lfloor\frac{x}{2}\rfloor$ 表示不大于 $\frac{x}{2}$ 的最大整数。
$\lceil\frac{x}{2}\rceil$ 表示不小于 $\frac{x}{2}$ 的最小整数。

输入包含多个测试用例。第一行包含一个整数 $t$ ( $1 \le t \le 10^4$ ) —— 测试用例的数量。接下来的行描述每个测试用例。

每个测试用例仅有一行，给出两个整数 $n$ 和 $k$ —— 分别表示巨大苹果堆中的苹果数量，以及安德烈希望在一个堆中得到的苹果数量 ( $1 \le n, k \le 10^9$ )。

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

4
10 3
11 5
21 4
1000000000 1

第一个测试用例 n=10, k=3：第一次分割后，得到两堆，每堆 5 个苹果。如果再将其中一堆分割，会得到一堆 2 个苹果和一堆 3 个苹果。总共需要 2 次分割，答案为 2。
第二个测试用例 n=11, k=5：第一次分割后，得到一堆 5 个苹果和一堆 6 个苹果。所以只需 1 次分割，答案为 1。
第三个测试用例 n=21, k=4：经过分割，只能得到大小为 1, 2, 3, 5, 6, 10, 11 或 21 的苹果堆，无法得到大小为 4 的堆，因此输出 -1。
第四个测试用例 n=1000000000, k=1：需要不断地将较大的堆分割，直到得到大小为 1 的堆。总共需要 29 分钟。