F. Small Operationstime limit per test3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputGiven an integer $$$x$$$ and an integer $$$k$$$. In one operation, you can perform one of two actions: choose an integer $$$1 \le a \le k$$$ and assign $$$x = x \cdot a$$$; choose an integer $$$1 \le a \le k$$$ and assign $$$x = \frac{x}{a}$$$, where the value of $$$\frac{x}{a}$$$ must be an integer. Find the minimum number of operations required to make the number $$$x$$$ equal to $$$y$$$, or determine that it is impossible.InputThe first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.The only line of each test case contains three integers $$$x$$$, $$$y$$$ and $$$k$$$ ($$$1 \le x, y, k \le 10^6$$$).It is guaranteed that the sum of $$$x$$$ and the sum of $$$y$$$ across all test cases does not exceed $$$10^8$$$.OutputFor each test case, output $$$-1$$$ if it is impossible to achieve $$$x=y$$$ using the given operations, and the minimum number of required operations otherwise.ExampleInput84 6 34 5 34 6 210 45 3780 23 4211 270 231 982800 131 6 2Output2
-1
-1
3
3
3
6
-1