對於一個整數 $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$。