For an integer $x$, you can perform the following operation any number of times:

Choose a base $k$ such that $2 \le k \le m$, write $x$ in base $k$, and "round" it so that the last digit becomes 0. Formally, in one operation, you can choose an integer $k$ ($2 \le k \le m$) and update $x$ to $f(x, k)$, where:

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

Given $m$, find the minimum number of operations required to change $x$ to $y$ for multiple queries.

Input

Each test file contains only one test case. The first line contains two integers $q$ and $m$ ($1 \le q \le 10^5, 2 \le m \le 10^5$), representing the number of queries and the maximum available base, respectively. The next $q$ lines each contain two integers $x$ and $y$ ($0 \le x, y \le 10^5, x \neq y$), representing the initial value and the target value for each query.

Output

For each query, output a single integer representing the minimum number of operations required to change $x$ to $y$. If $x$ cannot be changed to $y$ through these operations, output "-1".

Examples

Input 1

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

Output 1

2
-1
5
2
23

Note

For the first query in the example, one optimal operation sequence is: $4 \xrightarrow{k=5} 5 \xrightarrow{k=10} 10$. For the second query in the example, it is impossible to reach 11 from 3, so the output is -1. For the third query in the example, one optimal operation sequence is: $11 \xrightarrow{k=8} 8 \xrightarrow{k=6} 6 \xrightarrow{k=5} 5 \xrightarrow{k=4} 4 \xrightarrow{k=3} 3$. For the fourth query in the example, one optimal operation sequence is: $5 \xrightarrow{k=4} 4 \xrightarrow{k=10} 0$. For the fifth query in the example, one optimal operation sequence is: $1 \xrightarrow{k=2} 2 \xrightarrow{k=3} 3 \dots \xrightarrow{k=10} 72$.