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