给定一个整数 $$$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$$$。
输出
对于每个测试用例,如果使用给定操作不可能实现 $$$x=y$$$,则输出 $$$-1$$$,否则输出所需操作的最小数量。
示例
输入复制
84 6 34 5 34 6 210 45 3780 23 4211 270 231 982800 131 6 2
输出复制
2 -1 -1 3 3 3 6 -1