题目背景

幽灵

不属于这个世界

但因这个世界而诞生

潜藏在秩序之外

$$醒来吧，我的心是堡垒\\ 在梦中我易受伤害$$

题目描述

在 Madeline 的梦境中，城市的边境是由大大小小的宇宙碎片构成的。

每个宇宙碎片都有一定的能量值，由于碎片的大小有一定的差异，因此它们的能量值也有大有小。

Madeline 很享受在碎片之间穿梭，她每次都会选择两个宇宙碎片，并获得它们能量值的最大公约数的愉悦值。注意这两个宇宙碎片可以相同。

宇宙碎片构成了一段序列 $a_1,a_2,\cdots,a_n$，每次 Madeline 都会选择它的一个区间，对于这个区间里面的任意两个宇宙碎片 $(u,v)$，她都会进行一次穿梭。注意这里的 $(u,v)$ 是有序对。

形式化地，Madeline 每次获得的愉悦值为

$$\sum_{i=l}^r\sum_{j=l}^r \gcd(a_i,a_j)$$

当 Madeline 从她的梦中被唤醒时，她发现所有的宇宙碎片都消失了。她不记得在梦中每次穿梭时获得的愉悦值是多少，只依稀记得她选择的区间了。

于是她找到了你——一个信息学大佬，请你根据她每次选择的区间，还原她当时的愉悦值。

输入格式

第一行两个正整数 $n,q$，分别表示碎片个数以及询问数。

第二行有 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，表示每个碎片的能量值。

接下来 $q$ 行，每行两个整数 $l_i,r_i$，表示第 $i$ 次询问 Madeline 选择的区间。

输出格式

对于每个询问输出一行，表示在这次询问中，Madeline 获得的愉悦值的总和。

5 2
1 2 3 4 5
1 2
2 3

5
7

提示

• 对于 $10\%$ 的数据，满足 $n,q\leq 200$；
• 对于 $20\%$ 的数据，满足 $n,q\leq 2250$；
• 对于 $40\%$ 的数据，满足 $n,q\leq 4000$；
• 对于 $100\%$ 的数据，满足 $n,q,a_i\leq 10^5$。

保证数列和询问均为随机生成。