整数 $x$ に対して、以下の操作を任意の回数行うことができます。

$m$ 以下の整数 $k$ を選択し、$x$ を $k$ 進法で表したときの「四捨五入」を行い、$x$ の末尾を $0$ にします。形式的には、1 回の操作で整数 $k$ ($2 \le k \le m$) を選択し、$x$ を $f(x, k)$ に更新します。ここで $f(x, k)$ は以下のように定義されます。

$$ 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} $$

$x$ を $y$ に変えるために必要な最小の操作回数を求めてください。固定された $m$ に対して、複数のクエリに答える必要があります。

入力

各テストファイルには 1 つのテストデータのみが含まれます。

1 行目に 2 つの整数 $q$ と $m$ ($1 \le q \le 10^5, 2 \le m \le 10^5$) が与えられ、それぞれクエリの数と使用可能な最大の進数を表します。

続く $q$ 行の各行には、2 つの整数 $x$ と $y$ ($0 \le x, y \le 10^5, x \neq y$) が与えられ、各クエリの初期値と目標値を表します。

出力

各クエリについて、$x$ を $y$ に変えるために必要な最小の操作回数を 1 行に出力してください。操作によって $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$ です。