该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Apple

问题背景

一年一度的苹果品鉴会要开始了，噜噜在苹果园摘取了一些苹果带到了品鉴会。

问题描述

噜噜一共摘取了 $n$ 个苹果，品鉴会来了 $m$ 个品鉴大师，接下来要将这些苹果分给这些品鉴大师，噜噜是一个公平的水豚，所以将会把苹果 平均 分给这 $m$ 个品鉴大师。

很明显，分苹果的时候必然会出现要切割苹果的操作，在品鉴会上存在一把水果刀，这个水果刀在切割苹果的时候一定可以切割成两个重量相同的苹果块。

已知每个苹果的重量都是 $1$ kg，请问最少需要切几刀，才能将苹果 平分 给这些品鉴大师。

输入输出格式

输入格式

多组测试数据。 输入多行。 第一行输入一个正整数 $t$ ，代表测试组数量。 接下来 $t$ 行，每行输入两个正整数 $n, m$ ，分别代表初始噜噜采摘的苹果的数量，以及品鉴大师的数量。

输出格式

输出一行。 一行输出一个正整数，将 $n$ 个苹果分给 $m$ 人最少需要切割的次数，如果无法通过切割 平分 输出 $-1$ 。

输入输出样例

输入样例

4
10 5
1 5
10 4
3 4

输出样例

0
-1
2
5

数据范围与提示

对于 $100\%$ 的数据，保证 $1 \le t \le 10^5, 1 \le n, m \le 10^{12}$ 。

• 特殊性质 $A$ ：保证 $m | n$ 。
• 特殊性质 $B$ ：数据随机。