题目描述

有 $n$ 个硬币，初始时都是反面朝上，你需要使它们全变成正面朝上。你每次必须恰好翻转 $k$ 个硬币，求至少要翻转多少次，或说明永远不可能完成。

你觉得这个问题太简单了，于是你要求你的教练给你 $T$ 份这样的问题，想一次性解决。

注：翻转指正面变反面，反面变正面，不是将 $k$ 个硬币的次序颠倒。

输入格式

第一行包含一个正整数 $T$，表示数据组数。

对于每组数据，共一行，包含两个正整数 $n,k$，表示硬币数量和每次翻转的数量。

输出格式

对于每组数据，输出一行一个整数，如果永远不可能完成，则为 $-1$，否则为最少的操作次数。

样例一

输入

3
5 2
5 3
8 5

输出

-1
3
4

解释

对于第二组数据，一个可行的方法如下（用 $\circ$ 表示反面朝上，$\bullet$ 表示正面朝上）：

$$\circ\circ\circ\circ\circ \longrightarrow \bullet\bullet\bullet\circ\circ \longrightarrow \bullet\circ\circ\circ\bullet \longrightarrow \bullet\bullet\bullet\bullet\bullet$$

样例二

见原题“相关文件下载”中的 ex_coin2.in 与 ex_coin2.out。

限制与约定

对于所有的测试点，保证：

$$1\le T\le 2\times 10^5,\qquad 1\le k\le n\le 10^{18}.$$

• 对于前 $10\%$ 的数据，保证 $n\le 14$；
• 对于另外 $15\%$ 的数据，保证 $n\le 500$；
• 对于另外 $10\%$ 的数据，保证 $T=1$；
• 对于另外 $15\%$ 的数据，保证 $n$ 为奇数；
• 对于另外 $15\%$ 的数据，保证 $k\le \dfrac n2$；
• 对于另外 $20\%$ 的数据，保证 $n\le 10^9$。

时间限制：$1\text{s}$

空间限制：$512\text{MB}$