問題文

N 頂点の無向グラフがあります。このグラフの辺の情報は長さ N の数列 A を用いて、以下のように表されます。

• 任意の整数対 (i,j)\ (1 \leq i \lt j \leq N) について、
  • A_i と A_j が互いに素なら、頂点 i と頂点 j の間に辺は存在しない。
  • A_i と A_j が 1 より大きい公約数を持つなら、その中の最小値を x として頂点 i と頂点 j の間に長さ x の辺が存在する。

以下のクエリが Q 個与えられるので、順に処理してください。

• 頂点の組 (S,T) が与えられる。S と T が連結かを判定し、連結なら S から T へ向かう最短経路の長さを出力せよ。

制約

• 2 \leq N \leq 10^5
• 1 \leq Q \leq 2 \times 10^3
• 1 \leq A_i \leq 10^6 (1 \leq i \leq N)
• 各クエリにおいて、1 \leq S,T \leq N かつ S \neq T が満たされる
• 入力は全て整数

部分点

• Q=1 を満たすデータセットに正解した場合、500 点が与えられる。

注意

部分点のみを狙ったコードを提出する際には、Q が 1 より大きいならすぐ終了するといった処理を書き加えることを推奨します。

入力例 1

3 3
10 6 21
1 2
2 3
1 3

出力例 1

2
3
5

与えられる N=3 頂点のグラフには、以下の 2 本の辺が張られています。

• 頂点 1 と頂点 2 を結ぶ、長さ 2 の辺
• 頂点 2 と頂点 3 を結ぶ、長さ 3 の辺

よって各クエリに対する答えは以下の通りとなります。

• 1 個目のクエリにおいて問われている、頂点 1 と頂点 2 の最短距離は頂点 1 と頂点 2 を直接結ぶ辺の長さに等しく、その値は 2 である。
• 2 個目のクエリにおいて問われている、頂点 2 と頂点 3 の最短距離は頂点 2 と頂点 3 を直接結ぶ辺の長さに等しく、その値は 3 である。
• 3 個目のクエリにおいて問われている、頂点 1 と頂点 3 の最短距離は頂点 1,2 を結ぶ辺の長さと頂点 2,3 を結ぶ辺の長さの和に等しく、その値は 5 である。

入力例 2

2 1
1 1
1 2

出力例 2

-1

与えられるグラフにおいて頂点 1 と頂点 2 は非連結であるため、-1 を出力します。

なお、この入力は部分点の制約を満たします。

入力例 3

8 5
10 465 800 966 393 217 556 279
7 6
6 4
4 1
6 2
1 6

出力例 3

9
7
2
10
9

原案: primenumber_zz