Common Divisor Graph

Description:

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.

Output:

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}$$$.

Sample Input:

3 3
2 10 3
1 2
1 3
2 3

Sample Output:

0
1
1

Sample Input:

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

Sample Output:

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

Note:

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$$$.