题目描述

你有一个正整数 $x$，可以进行如下操作：

• 选择任意正整数 $y$，令 $x \gets x \times \gcd(x, y)$（其中 $\gcd(x, y)$ 表示 $x$ 和 $y$ 的最大公因数）。

初始时 $x = n$，目标是通过若干次操作（也可以不操作）使 $x = m$。求最少操作次数，或报告无解。

输入格式

本题包含多组测试数据。

第一行一个正整数 $T$，表示数据组数。

接下来 $T$ 行，每行两个正整数 $n, 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}$。