← 返回题目列表

Codeforces · 2114/F

F. 小操作

中文机器翻译题面 查看原题

给定一个整数 $$$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$$$,否则输出所需操作的最小数量。

示例

输入
复制

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