310716: CF1875C. Jellyfish and Green Apple

C. Jellyfish and Green Appletime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Jellyfish has $n$ green apple pieces. Each green apple piece weighs $1~\text{kg}$. Jellyfish wants to divide these green apple pieces equally among $m$ people.

Jellyfish has a magic knife. Each time Jellyfish can choose one piece of green apple and divide it into two smaller pieces, with each piece having half the weight of the original piece.

Jellyfish wants to know the minimum number of operations needed such that she can divide the green apple pieces such that the total weight of apple pieces received by each person is the same.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 2 \cdot 10^4$). The description of the test cases follows.

The first and only line of each test case contains two integers, $n$ and $m$ ($1 \leq n, m \leq 10^9$) — the number of the green apple pieces initially and the number of the people.

Output

For each test case, output a single integer — the minimum number of operations required to divide all the green apples equally among the $m$ people. If this cannot be achieved using a finite number of operations, output $-1$ instead.

ExampleInput

4
10 5
1 5
10 4
3 4

Output

0
-1
2
5

Note

In the first test case, we do not need to divide the apple pieces. Each person will receive $2$ pieces of $1~\text{kg}$ and the total weight of apple pieces received by each person is $2~\text{kg}$.

In the second test case, it is impossible to divide the apple equally using a finite number of operations.

In the third test case, we can divide two of the apple pieces of weight $1~\text{kg}$, getting $4$ apple pieces of weight $0.5~\text{kg}$. Each person will receive $1$ apple piece of weight $0.5~\text{kg}$ and $2$ apple pieces of weight $1~\text{kg}$. The total weight of apple pieces received by each person is $2.5~\text{kg}$.

In the fourth test case, we first divide all $3$ of the apple pieces of weight $1~\text{kg}$, getting $6$ pieces of weight $0.5~\text{kg}$. Then, we further divide two of the apple pieces of weight $0.5~\text{kg}$, getting $4$ pieces of weight $0.25~\text{kg}$. Each person will receive $1$ apple piece of weight $0.5~\text{kg}$ and $1$ apple piece of weight $0.25~\text{kg}$. The total weight of apples received by each person is $0.75~\text{kg}$.

题目大意：
Jellyfish有n块绿苹果，每块重1公斤。她想把这些苹果块平均分给m个人。Jellyfish有一把魔法刀，每次可以选择一块绿苹果并将其切成两块，每块重量是原来的一半。Jellyfish想知道最少的操作次数，以便她可以将绿苹果块平均分给每个人，如果无法用有限次操作达到目的，则输出-1。

输入输出数据格式：
输入：
- 第一行包含一个整数t（1≤t≤2×10^4），表示测试用例的数量。
- 每个测试用例包含一行，包含两个整数n和m（1≤n, m≤10^9），分别表示绿苹果块的数量和人数。

输出：
- 对于每个测试用例，输出一个整数，表示将所有绿苹果平均分给m个人所需的最少操作次数。如果不能实现，则输出-1。题目大意： Jellyfish有n块绿苹果，每块重1公斤。她想把这些苹果块平均分给m个人。Jellyfish有一把魔法刀，每次可以选择一块绿苹果并将其切成两块，每块重量是原来的一半。Jellyfish想知道最少的操作次数，以便她可以将绿苹果块平均分给每个人，如果无法用有限次操作达到目的，则输出-1。 输入输出数据格式： 输入： - 第一行包含一个整数t（1≤t≤2×10^4），表示测试用例的数量。 - 每个测试用例包含一行，包含两个整数n和m（1≤n, m≤10^9），分别表示绿苹果块的数量和人数。 输出： - 对于每个测试用例，输出一个整数，表示将所有绿苹果平均分给m个人所需的最少操作次数。如果不能实现，则输出-1。