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.

考虑一个由互不相同的整数 $a_1, \ldots, a_n$ 构成的序列，其中每个整数代表图中的一个节点。当且仅当两个数值不互质（即它们拥有大于 $1$ 的公共约数）时，这两个节点之间存在一条边。

共有 $q$ 个查询。在每次查询中，你需要从给定的起始节点 $a_s$ 到达目标节点 $a_t$。为实现该目标，你可以选择当前序列中某个已存在的值 $a_i$，并创建一个新值 $a_{n+1} = a_i \cdot (1 + a_i)$；该新节点与所有与其不互质的已有值之间均连边。同时，序列长度 $n$ 增加 $1$。你可以重复执行该操作多次，从而使得序列显著变长，并可能生成极大或重复的数值。问：使得 $a_t$ 从 $a_s$ 可达所需的最少新增节点数目是多少？

各查询相互独立。每次查询均从输入中给出的初始序列 $a$ 开始。

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.

第一行包含两个整数 $n$ 和 $q$（$2 \leq n \leq 150\,000$，$1 \leq q \leq 300\,000$）—— 分别表示序列的长度和查询次数。

第二行包含 $n$ 个互不相同的整数 $a_1, a_2, \ldots, a_n$（$2 \leq a_i \leq 10^6$，当 $i \neq j$ 时 $a_i \neq a_j$）。

接下来的 $q$ 行中，第 $j$ 行包含两个互不相同的整数 $s_j$ 和 $t_j$（$1 \leq s_j, t_j \leq n$，$s_j \neq t_j$）—— 表示第 $j$ 次查询所涉及的节点下标。

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

输出 $q$ 行。第 $j$ 行应包含一个整数：从 $a_{s_j}$ 移动到 $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$.

在第一个例子中，你可以首先创建新值 $2 \cdot 3 = 6$、$10 \cdot 11 = 110$ 或 $3 \cdot 4 = 12$。但在第一个查询中，这些操作均非必需，因为你已经可以直接从 $a_1 = 2$ 到达 $a_2 = 10$。

在第二个查询中，最优策略是先创建 $6$ 或 $12$。例如，创建 $6$ 后，即可通过路径 $(2, 6, 3)$ 从 $a_1 = 2$ 到达 $a_3 = 3$。

在第二个例子的最后一个查询中，我们需要从 $a_3 = 7$ 到达 $a_5 = 25$。一种可行的方法是：先创建 $6 \cdot 7 = 42$，再创建 $25 \cdot 26 = 650$。最终图包含七个节点，且其中存在一条从 $a_3 = 7$ 到 $a_5 = 25$ 的路径。