import math

def compute_sum(X, P):
    if X == 0:
        return 0
    sum_total = 0
    k_max = int(math.isqrt(P))
    if X <= k_max:
        for n in range(1, X + 1):
            sum_total += n * (P // n)
    else:
        for n in range(1, k_max + 1):
            sum_total += n * (P // n)
        max_k = P // (k_max + 1)
        for k in range(1, max_k + 1):
            m = (P // (k + 1)) + 1
            m_prime = P // k
            start = max(m, k_max + 1)
            end = min(m_prime, X)
            if start > end:
                continue
            count = end - start + 1
            sum_n = (start + end) * count // 2
            sum_total += k * sum_n
    return sum_total

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    P = int(input[ptr])
    ptr += 1
    Q = int(input[ptr])
    ptr += 1
    for _ in range(Q):
        L = int(input[ptr])
        ptr += 1
        R = int(input[ptr])
        ptr += 1
        if R > P:
            part1 = compute_sum(P, P)
            part2 = compute_sum(L-1, P)
            sum_total = part1 - part2
            sum_mod = (R - L + 1) * P - sum_total
        else:
            part1 = compute_sum(R, P)
            part2 = compute_sum(L-1, P)
            sum_total = part1 - part2
            sum_mod = (R - L + 1) * P - sum_total
        print(sum_mod)

if __name__ == '__main__':
    main()