Common Divisor Graph
Description
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}$.
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}$.
Samples
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
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$.