import math

def sum_floor_times_n(a, b, P):
    if a > b:
        return 0
    sum_total = 0
    sqrt_p = int(math.isqrt(P))
    
    # 处理k <= sqrt_p的情况
    for k in range(1, sqrt_p + 1):
        low = P // (k + 1) + 1
        high = P // k
        if high > b:
            high = b
        if low < a:
            low = a
        if low > high:
            continue
        # 计算sum n from low to high
        s = (high * (high + 1) // 2) - ((low - 1) * low // 2)
        sum_total += k * s
    
    # 处理k > sqrt_p的情况，此时n <= sqrt_p
    max_n = min(sqrt_p, b)
    for n in range(a, max_n + 1):
        k = P // n
        if k > sqrt_p:
            sum_total += k * 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
        a = max(L, 1)
        b = min(R, P)
        sum_r = sum_floor_times_n(1, b, P)
        sum_l_1 = sum_floor_times_n(1, L-1, P) if L > 1 else 0
        total = sum_r - sum_l_1
        ans = P * (R - L + 1) - total
        print(ans)

if __name__ == "__main__":
    main()