CF2114F Small Operations

Given 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.

The 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 $ .

For 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.