当前没有测试数据。

Description

给定一个长度为 $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}$ 的并集。

Format

Input

第一行两个整数 $n,m\ (1\leq n,m\leq 6\times 10^5)$ 表示序列大小和询问次数。

第二行 $n$ 个整数表示 $a_i\ (1\leq a_i\leq 2^{31})$。

接下来 $m$ 行，每行两个正整数 $l,r\ (1\leq l\leq r\leq n)$ 表示询问。

Output

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

Samples

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

2
2
2