F. Небольшие операции
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано целое число $$$x$$$ и целое число $$$k$$$. За одну операцию вы можете сделать одно из двух действий:

  • выбрать целое число $$$1 \le a \le k$$$ и присвоить $$$x = x \cdot a$$$;
  • выбрать целое число $$$1 \le a \le k$$$ и присвоить $$$x = \frac{x}{a}$$$, значение $$$\frac{x}{a}$$$ должно быть целым.

Найдите минимальное количество операций, необходимое, чтобы сделать число $$$x$$$ равным $$$y$$$, или определите, что это невозможно.

Входные данные

Первая строка входных данных содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Единственная строка каждого набора содержит три целых числа $$$x$$$, $$$y$$$ и $$$k$$$ ($$$1 \le x, y, k \le 10^6$$$).

Гарантируется, что сумма $$$x$$$ и сумма $$$y$$$ по всем наборам входных данных не превосходит $$$10^8$$$

Выходные данные

Для каждого набора входных данных выведите $$$-1$$$, если получить $$$x=y$$$ с помощью данных операций невозможно, и минимальное число необходимых операций, иначе.

Пример
Входные данные
8
4 6 3
4 5 3
4 6 2
10 45 3
780 23 42
11 270 23
1 982800 13
1 6 2
Выходные данные
2
-1
-1
3
3
3
6
-1