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