P11130 [MX-X5-T2] "GFOI Round 1" Interstellar

Original problem link: . --- > [Interstellar - PIKASONIC](https://music.163.com/#/song?id=1900207101)

You have a positive integer $x$, and you may perform the following operation on it: - Choose a positive integer $y$, and change $x$ to $\gcd(x, y)$ times itself, i.e., $x \gets x \times \gcd(x, y)$. (Here, $\gcd(x, y)$ denotes the greatest common divisor of $x$ and $y$.) The initial value of $x$ is $n$. You want to turn it into $m$ using some number of operations (possibly zero). You want to know the minimum number of operations needed to achieve the goal, or report that it is impossible.

**This problem has multiple test cases.** The first line contains a positive integer $T$, indicating the number of test cases. For each test case: The first line contains two positive integers $n, m$.

For each test case: - If it is impossible, i.e., no matter how you operate, $x$ can never become $m$, output $-1$. - Otherwise, output a single non-negative integer on one line, representing the minimum number of operations.

**Sample Explanation** For the first test case, no operation is needed, so the answer is $0$. For the second test case, you can choose $y = 6$, then $x$ becomes $2 \times \gcd(2, 6) = 4$. For the third test case, it is easy to prove that no matter what operations you do, you cannot achieve the goal, so output $-1$. For the fourth test case, you can: - Choose $y = 16$, then $x$ becomes $12 \times \gcd(12, 16) = 48$. - Choose $y = 6$, then $x$ becomes $48 \times \gcd(48, 6) = 288$. **Constraints** | Test Point ID | $n \le$ | $m \le$ | Score | | :-: | :-: | :-: | :-: | | $1$ | $100$ | $2 \times 10^3$ | $21$ | | $2$ | $2$ | $10^{18}$ | $17$ | | $3$ | $10^5$ | $10^5$ | $14$ | | $4$ | $10^7$ | $10^7$ | $16$ | | $5$ | $10^{18}$ | $10^{18}$ | $32$ | For all test cases, $1 \le T \le 2 \times 10^5$, $1 \le n \le m \le 10^{18}$. Translated by ChatGPT 5