题目背景

幽灵

不属于这个世界

但因这个世界而诞生

潜藏在秩序之外

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

题目描述

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

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

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

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

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

当 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$

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