该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制：1 Sec 内存限制：256 MB 输入文件：mod.in 输出文件：mod.out

定义数列 $a_n = P\bmod n$（$n=1,2,\dots$）。

对于每组给定的 $L_i,R_i$（$i=1,2,\dots,Q$），请计算 $\displaystyle\sum_{n=L_i}^{R_i}a_n$ 的值。

输入格式

第一行两个整数 $P$ 和 $Q$。

接下来 $Q$ 行，每行两个整数 $L_i$ 和 $R_i$ 表示一次询问。

输出格式

共输出 $Q$ 行，第 $i$ 行对应 $\displaystyle\sum_{n=L_i}^{R_i}a_n$ 的计算结果。

样例

样例 1

23 1
1 7

16

样例说明：

$\sum_{n=1}^7a_n=0+1+2+3+3+5+2=16$

样例 2

3000 4
7 36
1 2491
2934 3000
1542 5231

263
1465544
2211
7756611

样例说明：

存在 $P \lt R_i$ 的情况。

样例 3

319586423 10
88 861
4641915 12591875
40 93620
4 58503
41376643 99181970
8388 351105
4029987 4171876
184091372 270441885
45972 65554518
8313 52186

180038
34469822716416
2189413228
855085983
2015105445915363
30802594433
294723880788
7971861707449373
1053080394476134
663106681

数据范围

对于 20% 的数据，$Q=1$，$R_i \le 10^6$。

对于 100% 的数据，$1\le P\le10^9$，$1\le Q\le10^5$，$1\le L_i\le R_i\le 10^9$。