考虑一系列不同的整数 $$$a_1, \ldots, a_n$$$,每个整数代表图的一个节点。如果两个值不互质,则两个节点之间存在一条边,即。 e.它们的公约数大于$$$1$$$。
有 $$$q$$$ 查询,在每个查询中,您希望从一个给定节点 $$$a_s$$$ 到另一个 $$$a_t$$$。为了实现这一点,您可以选择现有值 $$$a_i$$$ 并创建新值 $$$a_{n+1} = a_i \cdot (1 + a_i)$$$,其边缘指向与 $$$a_{n+1}$$$ 不互质的所有值。此外,$$$n$$$ 增加了$$$1$$$。您可以多次重复该操作,这可能会使序列更长并获得巨大或重复的值。为了从 $$$a_s$$$ 可以到达 $$$a_t$$$,新创建的节点的最小可能数量是多少?
查询是独立的。在每个查询中,您从输入中给出的初始序列 $$$a$$$ 开始。
输入
第一行包含两个整数 $$$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$$$, $$$a_i \neq a_j$$$ if $$$i \ne j$$$)。
以下 $$$j$$$ 行中的第 $$$q$$$ 行包含两个不同的整数 $$$s_j$$$ 和 $$$t_j$$$ ($$$1 \leq s_j, t_j \leq n$$$, $$$s_j \neq t_j$$$) — 第 $$$j$$$ 查询的节点索引。
输出
打印 $$$q$$$ 行。第 $$$j$$$ 行应包含一个整数:为了从 $$$a_{s_j}$$$ 移动到 $$$a_{t_j}$$$,您创建的新节点的最小数量。
示例
输入 #1
3 3 2 10 3 1 2 1 3 2 3
输出 #1
0 1 1
输入 #2
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
输出 #2
0 1 0 1 0 1 0 1 1 1 1 2
注意
在第一个示例中,您可以先创建新值 $$$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$$$ 的路径。