题目描述

巨龙 Evirir 找到了 $n$ 个正整数 $a_1, a_2, \ldots, a_n$。它需要回答 $q$ 个形如 $(l, r)$ （$1 \le l \le r \le n$）的询问，每个询问的含义如下：

• 构造数组 $b = [b_1, b_2, \ldots, b_{r-l+1}] = [a_l, a_{l+1}, \ldots, a_r]$。在一次操作中，Evirir 可以选择 $b$ 中相邻的两个整数，设为 $b_i$ 和 $b_{i+1}$ （$1 \le i < r-l+1$），并将它们替换为一个整数 $\gcd(b_i, b_{i+1})$。要使 $b$ 中所有元素相等，最少需要多少次操作？

你能帮助它快速回答这些询问吗？

注意： $\gcd(x, y)$ 表示整数 $x$ 和 $y$ 的最大公约数（GCD）。例如， $\gcd(18, 12) = 6$， $\gcd(14, 6) = 2$， $\gcd(9, 14) = 1$。参见 https://en.wikipedia.org/wiki/Greatest_common_divisor

输入格式

第一行包含两个以空格分隔的整数 $n$ 和 $q$ （$1 \le n \le 60\,000$， $1 \le q \le 100\,000$）。

第二行包含 $n$ 个以空格分隔的整数 $a_1, a_2, \ldots, a_n$ （$1 \le a_i \le 60\,000$）。

接下来的 $q$ 行，每行包含两个整数 $l$ 和 $r$ （$1 \le l \le r \le n$），代表一个询问。

输出格式

按顺序对于每个询问，输出一行一个整数作为答案。

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

提示

注释

示例 1

对于第一个询问（$\texttt{1 7}$）， $b = [36, 24, 120, 24, 36, 60, 48]$。一种最优解法如下（被选中的元素以 $\underline{下划线}$ 标记，上一次操作产生的新元素以 $\textbf{粗体}$ 标记）：

• $[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]$

可以证明，无法在少于 $4$ 次操作内使所有元素相等。

对于第二个询问（$\texttt{2 4}$）， $b = [24, 120, 24]$。一种最优解法是 $[24, \underline{120, 24}] \to [24, \mathbf{24}]$。

对于第三个和第四个询问，可以不断合并直至只剩下一个元素。

对于第五个和第六个询问，$b$ 中所有元素已经相等。

计分

子任务 1 （$8$ 分）： $n \le 15$， $q \le 120$。

子任务 2 （$10$ 分）： $n, q \le 300$。

子任务 3 （$13$ 分）： $n, q \le 3000$。

子任务 4 （$17$ 分）： 对于所有 $1 \le i \le n$， $a_i \le 2$。

子任务 5 （$9$ 分）： 对于所有 $1 \le i \le n$，存在某个整数 $k \ge 0$ 使得 $a_i = 2^k$。

子任务 6 （$7$ 分）： $q = n$，且对于所有 $1 \le i \le q$，第 $i$ 个询问是 $(1, i)$。

子任务 7 （$26$ 分）： 对于所有 $1 \le i \le n$， $a_i \le 36$。

子任务 8 （$10$ 分）： 无额外限制。

翻译由 DeepSeek 完成