Common Divisor Graph

给定一个包含 $n$ 个节点的图。第 $i$ 个节点都有权值 $a_i$，没有两个节点权值相同。节点 $i,j$ 之间有一条无向边仅当 $\gcd(a_i,a_j)>1$。 给定 $q$ 次询问，每次包含整数 $s,t$ 表示你希望从节点 $s$ 到达节点 $t$。为了到达那个节点，你可以进行下列操作任意次： - 选定一个节点 $i$。创造一个新的节点，该节点的权值为 $a_i\times(a_i+1)$，并按照上述规则连边。 对于每次询问，你都需要求出，至少需要多少次操作才能使节点 $s$ 能到达节点 $t$。询问互相独立。 $2\leq n\leq1.5\times10^5;1\leq q\leq3\times10^5;$ $2\leq a_i\leq10^6;$ 且如果 $i\not=j$，$a_i\not=a_j$。 $1\leq s,t\leq n;s\not=t;$

Consider a sequence of distinct integers $ a_1, \ldots, a_n $ , each representing one node of a graph. There is an edge between two nodes if the two values are not coprime, i. e. they have a common divisor greater than $ 1 $ . There are $ q $ queries, in each query, you want to get from one given node $ a_s $ to another $ a_t $ . In order to achieve that, you can choose an existing value $ a_i $ and create new value $ a_{n+1} = a_i \cdot (1 + a_i) $ , with edges to all values that are not coprime with $ a_{n+1} $ . Also, $ n $ gets increased by $ 1 $ . You can repeat that operation multiple times, possibly making the sequence much longer and getting huge or repeated values. What's the minimum possible number of newly created nodes so that $ a_t $ is reachable from $ a_s $ ? Queries are independent. In each query, you start with the initial sequence $ a $ given in the input.

The first line contains two integers $ n $ and $ q $ ( $ 2 \leq n \leq 150\,000 $ , $ 1 \leq q \leq 300\,000 $ ) — the size of the sequence and the number of queries. The second line contains $ n $ distinct integers $ a_1, a_2, \ldots, a_n $ ( $ 2 \leq a_i \leq 10^6 $ , $ a_i \neq a_j $ if $ i \ne j $ ). The $ j $ -th of the following $ q $ lines contains two distinct integers $ s_j $ and $ t_j $ ( $ 1 \leq s_j, t_j \leq n $ , $ s_j \neq t_j $ ) — indices of nodes for $ j $ -th query.

Print $ q $ lines. The $ j $ -th line should contain one integer: the minimum number of new nodes you create in order to move from $ a_{s_j} $ to $ a_{t_j} $ .

3 3
2 10 3
1 2
1 3
2 3

0
1
1

5 12
3 8 7 6 25
1 2
1 3
1 4
1 5
2 1
2 3
2 4
2 5
3 1
3 2
3 4
3 5

0
1
0
1
0
1
0
1
1
1
1
2

In the first example, you can first create new value $ 2 \cdot 3 = 6 $ or $ 10 \cdot 11 = 110 $ or $ 3 \cdot 4 = 12 $ . None of that is needed in the first query because you can already get from $ a_1 = 2 $ to $ a_2 = 10 $ . In the second query, it's optimal to first create $ 6 $ or $ 12 $ . For example, creating $ 6 $ makes it possible to get from $ a_1 = 2 $ to $ a_3 = 3 $ with a path $ (2, 6, 3) $ . In the last query of the second example, we want to get from $ a_3 = 7 $ to $ a_5 = 25 $ . One way to achieve that is to first create $ 6 \cdot 7 = 42 $ and then create $ 25 \cdot 26 = 650 $ . The final graph has seven nodes and it contains a path from $ a_3 = 7 $ to $ a_5 = 25 $ .