题目描述

模拟宇宙迎来了一次更新，开拓了一片无尽的星域。

这片星域没有尽头，分布着编号为 $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$。

3
1 1
2 8
2 3

0
1
-1

提示

对于第一组数据，起点和终点都是区域 $1$，因此答案为 $0$。

对于第二组数据，因为 $2 \times 8 = 16 = 4^2$，所以可以直接从区域 $2$ 到达区域 $8$，答案为 $1$。

对于第三组数据，不存在任何起点为区域 $2$，终点为区域 $3$ 的路径，因此答案为 $-1$。