小辰刚学 gcd

题号：NC263123
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个长度为 $n$ 的数组 $a=[a_1,a_2,\cdots ,a_n]$ 。

对数组进行多次查询，每次查询数组的一个连续区间 $[l,r]$ ，需要计算集合 $S=\bigcup_{i=l}^{r}{\left\{\text{gcd}_{j=i}^r{a_j}\right\}}$ 的大小。

注意： $\text{gcd}_{i=p}^{q}{a_i}$ 表示数组 $a$ 中 $a_p,a_{p+1},\cdots ,a_{q}$ 的最大公因数， $\bigcup_{i=p}^{q}{s_i}$ 表示集合 $s_p,s_{p+1},\cdots s_{q}$ 的并集。

输入描述:

第一行两个整数  表示序列大小和询问次数。

第二行  个整数表示 。

接下来  行，每行两个正整数  表示询问。

输出描述:

共  行，每行一个正整数表示答案。

示例1

输入

复制

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

输出

复制

2
2
2