Problem Description

There is an undirected graph with $ N $ vertices. The edge information of this graph is represented using an array $ A $ of length $ N $ as follows:

• For any pair of integers $(i,j)\ (1\ \leq\ i\ \lt\ j\ \leq\ N)$,
• If $ A_i $ and $ A_j $ are coprime, there is no edge between vertex $ i $ and vertex $ j $.
• If $ A_i $ and $ A_j $ have a common divisor greater than $ 1 $, let the smallest such divisor be $ x $. There is an edge of length $ x $ between vertex $ i $ and vertex $ j $.

You are given $ Q $ queries, which should be processed in order.

• A pair of vertices $ (S,T) $ is given. Determine if $ S $ and $ T $ are connected, and if they are, output the length of the shortest path from $ S $ to $ T $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ Q $ $ A_1 $ $ A_2 $ $\ldots$ $ A_N $ $\text{query}_1$ $\text{query}_2$ $\hspace{0.4cm}\vdots$ $\text{query}_Q$

The content of the $ i $-th query is represented by $\text{query}_i$ and is given in the following format:

$ S $ $ T $

Output Format

Output $ Q $ lines. The $ i $-th line should contain the answer to the $ i $-th query as follows:

• If $ S $ and $ T $ are connected, output the length of the shortest path from $ S $ to $ T $.
• If $ S $ and $ T $ are not connected, output -1.

Sample Input and Output

Sample Input #1

3 3
10 6 21
1 2
2 3
1 3

Sample Output #1

2
3
5

Sample Input #2

2 1
1 1
1 2

Sample Output #2

-1

Sample Input #3

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

Sample Output #3

9
7
2
10
9

Notes/Hints

Constraints

• $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)$
• For each query, $1\ \leq\ S,T\ \leq\ N$ and $S\ \neq\ T$ are satisfied
• All inputs are integers

Partial Points

• If you solve the dataset where $ Q=1 $ correctly, you will be awarded $ 500 $ points.

Note

When submitting code aiming only for partial points, it is recommended to add a process that terminates immediately if $ Q $ is greater than $ 1 $.

Sample Explanation 1

The given graph with $ N=3 $ vertices has the following $ 2 $ edges:
- An edge of length $ 2 $ connecting vertex $ 1 $ and vertex $ 2 $
- An edge of length $ 3 $ connecting vertex $ 2 $ and vertex $ 3 $
Thus, the answers for each query are as follows:
- For the first query, the shortest distance between vertex $ 1 $ and vertex $ 2 $ is equal to the length of the edge directly connecting them, which is $ 2 $.
- For the second query, the shortest distance between vertex $ 2 $ and vertex $ 3 $ is equal to the length of the edge directly connecting them, which is $ 3 $.
- For the third query, the shortest distance between vertex $ 1 $ and vertex $ 3 $ is equal to the sum of the lengths of the edges connecting vertex $ 1 $ to vertex $ 2 $ and vertex $ 2 $ to vertex $ 3 $, which is $ 5 $.

Sample Explanation 2

In the given graph, vertex $ 1 $ and vertex $ 2 $ are not connected, so output -1. Note that this input satisfies the partial points constraint.

Sample Explanation 3

Original idea: primenumber_zz

见题面 Input 部分

见题面 Output 部分