【MX-X5-T2】「GFOI Round 1」Interstellar

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

你有一个正整数 $x$，你可以对它进行如下操作： - 选择一个正整数 $y$，把 $x$ 变为它的 $\gcd(x, y)$ 倍，即 $x \gets x \times \gcd(x, y)$。 （$\gcd(x, y)$ 表示 $x, y$ 的最大公因数。） $x$ 的初始值为 $n$，你想通过若干次操作（也可不操作）将它变为 $m$。你想知道至少要多少次操作才能达成目标，或报告无解。

**本题有多组测试数据。** 第一行输入一个正整数 $T$，表示测试数据组数。 对于每组测试数据： 第一行包含两个正整数 $n, m$。

对于每组数据： - 若无解，即 $x$ 无论如何操作都不能变成 $m$，输出 $-1$。 - 否则输出一行一个非负整数，表示最小的操作次数。

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

0
1
-1
2
3
-1

**【样例解释】** 对于第一组数据，无需进行任何操作，答案是 $0$。 对于第二组数据，可以选择 $y = 6$，那么 $x$ 会变成 $2 \times \gcd(2, 6) = 4$。 对于第三组数据，容易证明无论如何进行操作都不可能达成目标，所以输出 $-1$。 对于第四组数据，可以： - 选择 $y = 16$，那么 $x$ 会变成 $12 \times \gcd(12, 16) = 48$； - 选择 $y = 6$，那么 $x$ 会变成 $48 \times \gcd(48, 6) = 288$。 **【数据范围】** | 测试点编号 | $n \le$ | $m \le$ | 分值 | | :-: | :-: | :-: | :-: | | $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$ | 对于所有数据，满足 $1 \le T \le 2 \times 10^5$，$1 \le n \le m \le 10^{18}$。