Background

Original problem link: https://oier.team/problems/X5C.

Interstellar - PIKASONIC

Problem Description

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.

Input Format

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

Output Format

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.

6
1 1
2 4
2 6
12 288
30 144000
114 5141919810

0
1
-1
2
3
-1

Hint

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

For all test cases, $1 \le T \le 2 \times 10^5$, $1 \le n \le m \le 10^{18}$.

Translated by ChatGPT 5