题目描述

给出一个长度为 $n$ 的序列 $A$。

一共有 $m$ 个询问，每个询问有两个参数 $l,r$，表示询问：

$$\sum_{i=l}^{r} \sum_{j=l}^{r} \omega(\gcd(A_i, A_j))$$

其中，$\omega(x)$ 表示 $x$ 的不同质因子个数。

输入格式

• 第一行两个正整数 $n, m$，描述序列长度和询问个数。
• 第二行一共 $n$ 个数，描述 $A_1, A_2, A_3, \ldots, A_n$。
• 接下来 $m$ 行，每行两个正整数 $l, r$，描述一个询问。

输出格式

一共 $m$ 行，每行一个数，表示对应询问的答案。

一行一个数表示答案。

Samples

5 3
4 6 8 9 10
2 4
1 3
3 5

8
10
6