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