F. 小型操作
每次测试的时间限制：3 秒
每次测试的内存限制：256 兆字节

给定一个整数 $x$ 和一个整数 $k$。在一次操作中，你可以选择以下两种操作之一：

1. 选择一个整数 $1 \le a \le k$，并令 $x = x \cdot a$；
2. 选择一个整数 $1 \le a \le k$，并令 $x = \frac{x}{a}$，其中 $\frac{x}{a}$ 必须为整数。

要求通过最少的操作次数使得数 $x$ 变为 $y$，如果不可能实现，则输出 $-1$。

输入
第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。
每个测试用例一行，包含三个整数 $x$、$y$ 和 $k$（$1 \le x, y, k \le 10^6$）。
保证所有测试用例的 $x$ 的和与 $y$ 的和均不超过 $10^8$。

输出
对于每个测试用例，如果不可能通过给定操作使得 $x = y$，输出 $-1$，否则输出所需的最少操作次数。

示例
输入

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