题目背景

Interstellar - PIKASONIC

题目描述

你有一个正整数 $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$。

【数据范围】

对于所有数据，满足 $1 \le T \le 2 \times 10^5$，$1 \le n \le m \le 10^{18}$。