import sys
import math

def main():
    input = sys.stdin.read().split()
    idx = 0
    P = int(input[idx])
    idx += 1
    Q = int(input[idx])
    idx += 1
    queries = []
    for _ in range(Q):
        L = int(input[idx])
        R = int(input[idx+1])
        queries.append((L, R))
        idx += 2
    
    K = int(math.isqrt(P))
    
    for L, R in queries:
        L_prime = max(L, 1)
        R_prime = min(R, P)
        if L_prime > R_prime:
            total = 0
        else:
            sum_small = 0
            for k in range(1, K + 1):
                m = (P // (k + 1)) + 1
                M = P // k
                a = max(m, L_prime)
                b = min(M, R_prime)
                if a > b:
                    continue
                count = b - a + 1
                sum_n = (a + b) * count // 2
                sum_small += k * sum_n
            
            sum_large = 0
            a = max(L_prime, 1)
            b = min(R_prime, K)
            if a <= b:
                for n in range(a, b + 1):
                    k = P // n
                    if k > K:
                        sum_large += n * k
            
            total = sum_small + sum_large
        
        result = (R - L + 1) * P - total
        print(result)

if __name__ == '__main__':
    main()