gcd 完备

所有输入均从 gcd.in 读取，所有输出均写入 gcd.out。

时间限制：$4$ 秒。内存限制：$256$ MiB。

题目描述

给定一个长度为 $n$ 的正整数序列 $a_1,a_2,\ldots,a_n$，其中的数两两不同。

对于一个区间 $[L,R]$，如果任选两个不同的位置 $i,j$，其中 $L\le i<j\le R$，都能在这个区间中找到一个位置 $k$，使得 $a_k=\gcd(a_i,a_j)$，就称 $[L,R]$ 为完整段。这里 $\gcd(x,y)$ 表示 $x,y$ 的最大公约数，$k$ 可以等于 $i$ 或 $j$。只包含一个元素的区间总是完整段。

有 $q$ 次询问。每次给定一个区间 $[l,r]$，请你求出满足 $l\le L\le R\le r$ 的完整段 $[L,R]$ 的数量。

输入格式

第一行包含两个正整数 $n,q$。

第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

接下来 $q$ 行，每行包含两个正整数 $l,r$，表示一次询问。

输出格式

输出 $q$ 行，每行一个整数，按照输入顺序给出每次询问的答案。

样例

样例 1

输入：

4 3
6 2 3 1
1 3
1 4
2 4

输出：

4
8
5

对于第一个询问，三个只含一个元素的区间都是完整段，$[1,2]$ 也是完整段，因此答案为 $4$。

区间 $[2,3]$ 不是完整段，因为 $\gcd(2,3)=1$，而这个区间中没有 $1$。

附加样例

样例 2 见 $\texttt{down/gcd2.in}$ 与 $\texttt{down/gcd2.ans}$，满足测试点 $5\sim6$ 的限制。

样例 3 见 $\texttt{down/gcd3.in}$ 与 $\texttt{down/gcd3.ans}$，满足测试点 $7\sim8$ 的限制。

样例 4 见 $\texttt{down/gcd4.in}$ 与 $\texttt{down/gcd4.ans}$，满足测试点 $9\sim12$ 的限制。

样例 5 见 $\texttt{down/gcd5.in}$ 与 $\texttt{down/gcd5.ans}$，满足测试点 $17\sim20$ 的限制。

数据范围

对于所有测试点，$1\le n,q\le2\times10^5$，$1\le a_i\le4\times10^5$，$a_1,a_2,\ldots,a_n$ 两两不同，且每次询问满足 $1\le l\le r\le n$。

特殊性质 $A$：对于任意 $1\le i<j\le n$，至少有 $a_i\mid a_j$、$a_j\mid a_i$ 中的一个成立。

特殊性质 $B$：每次询问都满足 $l=1$。