AT_tkppc6_2_j.Common Divisors Shortest Path Queries

给定一个由 $N$ 个顶点组成的无向图。图的边信息由长度为 $N$ 的数列 $A$ 表示，具体如下：

• 对于任意的整数对 $(i,j)$$（1\le i<j\le N）$，如果 $A_i$ 和 $A_j$ 互质，则顶点 $i$ 和顶点 $j$ 不相连。
• 如果 $A_i$ 和 $A_j$ 有大于 $1$ 的公约数，取这些公约数中的最小值作为 $x$，则顶点 $i$ 和顶点 $j$ 之间有一条长度为 $x$ 的边。

总共有 $Q$ 次查询，给定顶点对 $(S,T)$，判断 $S$ 和 $T$ 是否连通，若连通则输出从 $S$ 到 $T$ 的最短路径长度；否则输出 -1。

输入通过标准输入给出，具体格式如下：

$ N $ $ Q $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ \text{query}_1 $ $ \text{query}_2 $ $ \cdots $ $ \text{query}_Q $

第 $i$ 个查询的内容由 $ \text{query}_i $ 表示，格式如下：

$ S $ $ T $

输出通过标准输出给出，具体格式如下：

按顺序输出 $Q$ 行。第 $i$ 行表示第 $i$ 个查询的答案，具体如下：

• 如果顶点 $S$ 和顶点 $T$ 连通，则输出从 $S$ 到 $T$ 的最短路径长度。
• 如果顶点 $S$ 和顶点 $T$ 不连通，则输出 -1。