## https://yukicoder.me/problems/no/752 import math def f(n): return (n * (n + 1)) // 2 def fnc(r, cum_array, array, cum_array2, sqrt_p, P): if r <= sqrt_p: return cum_array[r] ans = cum_array[-1] q = P // r if q + 1 < len(cum_array2): ans += cum_array2[q + 1] end = array[q][1] a = P * r - q * f(r) a -= P * end - q * f(end) return ans + a def main(): P, Q = map(int, input().split()) lr = [] for _ in range(Q): l, r = map(int, input().split()) lr.append((l, r)) # 下準備 sqrt_p = int(math.sqrt(P)) ## sqrt_p以下 cum_array = [0] * (sqrt_p + 1) c = 0 for j in range(1, sqrt_p + 1): x = P % j c += x cum_array[j] = c # sqrt_p以上 array = [(10 ** 18, P, 0)] for q in range(1, sqrt_p + 1): start = P // q end = P // (q + 1) end = max(end, sqrt_p) x = (start - end) * P y = q * (f(start) - f(end)) x -= y array.append((start, end, x)) cum_array2 = [0] * (sqrt_p + 1) c = 0 for j in reversed(range(sqrt_p + 1)): c += array[j][2] cum_array2[j] = c for l, r in lr: valr = fnc(r, cum_array, array, cum_array2, sqrt_p, P) vall = fnc(l - 1, cum_array, array, cum_array2, sqrt_p, P) print(valr - vall) if __name__ == "__main__": main()