P17840 无尽星域

模拟宇宙迎来了一次更新，开拓了一片无尽的星域。 这片星域没有尽头，分布着编号为 $1,2,3,\dots$ 的无限多的区域。 对于两个不同的区域 $i$ 和 $j$，它们可以互相通行的条件是 $i$ 与 $j$ 的乘积为完全平方数$^{1}$。 现在，你正身处区域 $s$，并希望到达区域 $t$。 请求出，至少需要经过几个区域才能到达（起点区域 $s$ 不计入经过的区域数量）。 $^{1}$完全平方数是指可以表示为某个整数平方的正整数。例如，$1,4,9,16,25$ 都是完全平方数，而 $2,3,5$ 不是。

第一行一个整数 $T$（$1 \leq T \leq 100$），表示有 $T$ 组数据。 而后 $T$ 行，每行两个整数 $s$ 和 $t$（$1 \leq s \times t \leq 10^6$），表示这组数据中你要从 $s$ 前往 $t$。

$T$ 行，每行一个整数，表示至少需要经过几个区域。 **如果不可能到达目标区域，请输出** $-1$。

对于第一组数据，起点和终点都是区域 $1$，因此答案为 $0$。 对于第二组数据，因为 $2 \times 8 = 16 = 4^2$，所以可以直接从区域 $2$ 到达区域 $8$，答案为 $1$。 对于第三组数据，不存在任何起点为区域 $2$，终点为区域 $3$ 的路径，因此答案为 $-1$。