Problem C. 想起那段记忆吧！

时间限制：1000ms

空间限制：256MB

题目描述

沃兹基是一种非常神奇的生物。从出生起他会有 $n$ 段记忆，可以用 $1 \sim n$ 这 $n$ 个整数表示每一段记忆。

研究表明，如果连续若干段记忆的最大公约数值(gcd)为 1，那么沃兹基就可以回想起来这些记忆。

现在给定区间 $[l, r]$，请问沃兹基能回想起多少种不同的连续记忆段。当记忆段的起点或者终点不同时就被认为是不同的。

更正式的说：有一个长度为 $n$ 的序列 $[1, 2, 3, ..., n]$，给定区间 $[l, r]$ ，请问在这个区间内有多少组连续子序列满足gcd值为1.

输入描述

第一行输入两个整数 $n$ 和 $T$，分别代表总段数和询问组数。

接下来 $T$ 行输入两个整数 $l$ 和 $r$，代表每次询问的区间。

输出描述

输出 $T$ 行，每行一个整数，代表该组区间内满足条件的连续子序列数量。

样例1

输入

5 4
2 3
2 4
2 5
4 4

输出

1
3
6
0

样例1解释

对于第二组询问，满足条件的连续子序列有 $[2,3]$, $[3,4]$, $[2, 3, 4]$；$[2]$ 的gcd值为2，$[3]$ 的gcd值为3，都不满足条件；

对于第二组询问，满足条件的连续子序列有 $[2,3]$, $[3,4]$, $[4, 5]$, $[2, 3, 4]$, $[3, 4, 5]$, $[2, 3, 4, 5]$.

数据范围与约定

$1 \le n \le 10^9$, $1 \le T \le min(10^5, \frac{n * (n+1)}{2})$;

$1 \le l \le r \le n$.