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.

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.

Output

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

Note

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

$\text{[math]}$

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

Common Divisor Graph

Examples