Description

Evirir the dragon found $n$ positive integers $a_1, a_2, \ldots, a_n$. They want to answer $q$ queries of the form $(l, r)$ ($1 \le l \le r \le n$), which means:

• Construct the array $b = [b_1, b_2, \ldots, b_{r-l+1}] = [a_l, a_{l+1}, \ldots, a_r]$. In one operation, Evirir can choose two adjacent integers in $b$, say $b_i$ and $b_{i+1}$ ($1 \le i < r-l+1$), and replace them with one integer $\gcd(b_i, b_{i+1})$. What is the minimum number of operations needed to make all elements in $b$ equal?

Can you help them answer the queries fast?

Note: $\gcd(x, y)$ denotes the greatest common divisor (GCD) of integers $x$ and $y$. For example, $\gcd(18, 12) = 6$, $\gcd(14, 6) = 2$, and $\gcd(9, 14) = 1$. See https://en.wikipedia.org/wiki/Greatest_common_divisor

Input Format

The first line contains two space-separated integers $n$ and $q$ ($1 \le n \le 60\,000$, $1 \le q \le 100\,000$).

The second line contains $n$ space-separated integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 60\,000$).

Each of the following $q$ lines contains two integers $l$ and $r$ ($1 \le l \le r \le n$), representing a query.

Output Format

For each query in order, output an integer (the answer) on a line.

10 6
36 24 120 24 36 60 48 24 24 9
1 7
2 4
6 10
6 8
8 9
10 10

4
1
4
2
0
0

Hint

Note

$\underline{Example 1}$

For the first query ($\texttt{1 7}$), $b = [36, 24, 120, 24, 36, 60, 48]$. One optimal solution is (chosen elements are $\underline{underlined}$, the new element from the last operation is $\textbf{bolded}$):

• $[36, 24, \underline{120, 24}, 36, 60, 48]$: $\gcd(120, 24) = 24$
• $[36, 24, \mathbf{24}, 36, \underline{60, 48}]$: $\gcd(60, 48) = 12$
• $[\underline{36, 24}, 24, 36, \mathbf{12}]$: $\gcd(36, 24) = 12$
• $[\mathbf{12}, \underline{24, 36}, 12]$: $\gcd(24, 36) = 12$
• $[12, \mathbf{12}, 12]$

It can be proven that one cannot make all elements equal in fewer than 4 operations.

For the second query ($\texttt{2 5}$), $b = [24, 120, 24]$. One optimal solution is $[24, \underline{120, 24}] \to [24, \mathbf{24}]$.

For the third and fourth query, one can keep merging until one element is left.

For the fifth and sixth query, all elements of $b$ are already equal.

Scoring

Subtask 1 ($8$ points): $n \le 15$, $q \le 120$.

Subtask 2 ($10$ points): $n, q \le 300$.

Subtask 3 ($13$ points): $n, q \le 3000$.

Subtask 4 ($17$ points): For all $1 \le i \le n$, $a_i \le 2$.

Subtask 5 ($9$ points): For all $1 \le i \le n$, $a_i = 2^k$ for some integer $k \ge 0$.

Subtask 6 ($7$ points): $q = n$. For all $1 \le i \le q$, the $i$-th query is $(1, i)$.

Subtask 7 ($26$ points): For all $1 \le i \le n$, $a_i \le 36$.

Subtask 8 ($10$ points): No additional constraints.