CF1553G.Common Divisor Graph

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

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