Dla danej liczby całkowitej $x$ możesz wykonać następującą operację dowolną liczbę razy:

Wybierz podstawę systemu liczbowego $k$ nieprzekraczającą $m$, zapisz $x$ w systemie o podstawie $k$, a następnie „zaokrąglij” $x$ tak, aby jego ostatnia cyfra wynosiła 0. Formalnie, w jednej operacji możesz wybrać liczbę całkowitą $k$ ($2 \le k \le m$), a następnie zmienić $x$ na $f(x, k)$, gdzie:

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

Oblicz, ile operacji potrzeba, aby zmienić $x$ na $y$. Dla ustalonego $m$ musisz odpowiedzieć na wiele zapytań.

Wejście

Każdy plik testowy zawiera tylko jeden zestaw danych testowych.

Pierwsza linia zawiera dwie liczby całkowite $q$ oraz $m$ ($1 \le q \le 10^5$, $2 \le m \le 10^5$), oznaczające odpowiednio liczbę zapytań oraz maksymalną dostępną podstawę systemu.

Następnie $q$ linii, z których każda zawiera dwie liczby całkowite $x$ oraz $y$ ($0 \le x, y \le 10^5$, $x \neq y$), reprezentujące początkową i docelową wartość dla danego zapytania.

Wyjście

Dla każdego zapytania wypisz w jednej linii liczbę całkowitą oznaczającą minimalną liczbę operacji potrzebnych do przekształcenia $x$ w $y$. Jeśli przekształcenie $x$ w $y$ nie jest możliwe, wypisz „-1”.

Przykład

Wejście 1

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

Wyjście 1

2
-1
5
2
23

Uwagi

Dla pierwszego zapytania z przykładu, jednym z optymalnych rozwiązań jest: $4 \xrightarrow{k=5} 5 \xrightarrow{k=10} 10$.

Dla trzeciego zapytania z przykładu, jednym z optymalnych rozwiązań jest: $11 \xrightarrow{k=8} 8 \xrightarrow{k=6} 6 \xrightarrow{k=5} 5 \xrightarrow{k=4} 4 \xrightarrow{k=3} 3$.

Dla czwartego zapytania z przykładu, jednym z optymalnych rozwiązań jest: $5 \xrightarrow{k=4} 4 \xrightarrow{k=10} 0$.