“根据鸽巢原理，至少有一个屋子有两个人。 ——炸鸡块君”

对于一个整数 $x$，你可以进行以下操作任意次：

选择一个不超过 $m$ 的进制 $k$，将 $x$ 写作 $k$ 进制的形式，然后“四舍五入”使得 $x$ 的最低位为 $0$。形式化地说，在一次操作中，你可以选择一个整数 $k$ ($2 \le k \le m$)，然后令 $x$ 变为 $f(x, k)$，其中：

$$f(x, k) = \begin{cases} \lfloor \frac{x}{k} \rfloor \cdot k & x \bmod k < \frac{k}{2} \\ \lceil \frac{x}{k} \rceil \cdot k & x \bmod k \ge \frac{k}{2} \end{cases}$$

请问，要将 $x$ 变为 $y$，至少需要几次操作？对于一个固定的 $m$，你需要回答多个询问。

输入格式

每个测试文件仅有一组测试数据。

第一行包含两个整数 $q$ 和 $m$ ($1 \le q \le 10^5, 2 \le m \le 10^5$)，分别表示询问的数量和最大可用的进制。

接下来 $q$ 行，每行两个整数 $x$ 和 $y$ ($0 \le x, y \le 10^5, x \neq y$)，表示一个询问的初始数值和目标数值。

输出格式

对于每个询问，输出一行一个整数，表示将 $x$ 变为 $y$ 所需要的最小操作次数。如果 $x$ 不能通过操作变为 $y$，请输出 “-1”。

样例

输入样例 1

5 10
4 10
3 11
11 3
5 0
1 72

输出样例 1

2
-1
5
2
23

备注

对于样例的第 1 个询问，一种最优的操作方案为：$4 \xrightarrow{k=5} 5 \xrightarrow{k=10} 10$。

对于样例的第 3 个询问，一种最优的操作方案为：$11 \xrightarrow{k=8} 8 \xrightarrow{k=6} 6 \xrightarrow{k=5} 5 \xrightarrow{k=4} 4 \xrightarrow{k=3} 3$。

对于样例的第 4 个询问，一种最优的操作方案为：$5 \xrightarrow{k=4} 4 \xrightarrow{k=10} 0$。