Для целого числа $x$ вы можете выполнить следующую операцию любое количество раз:
Выберите основание системы счисления $k$, не превышающее $m$, запишите $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
6 10 5 10 4 10 3 11 11 3 5 0 1 72
Выходные данные 1
2 -1 5 2 23 -1
Примечание
Для первого запроса из примера один из оптимальных вариантов действий: $5 \xrightarrow{k=10} 10$.
Для третьего запроса из примера один из оптимальных вариантов действий: $3 \xrightarrow{k=4} 4 \xrightarrow{k=5} 5 \xrightarrow{k=6} 6 \xrightarrow{k=8} 8 \xrightarrow{k=11} 11$.
Для четвертого запроса из примера один из оптимальных вариантов действий: $11 \xrightarrow{k=8} 8 \xrightarrow{k=6} 6 \xrightarrow{k=5} 5 \xrightarrow{k=4} 4 \xrightarrow{k=3} 3$.
Для пятого запроса из примера один из оптимальных вариантов действий: $5 \xrightarrow{k=4} 4 \xrightarrow{k=10} 0$.