import sys

def compute_sum(L, R, P):
    res = 0
    current = L
    while current <= R:
        k = P // current
        if k == 0:
            m = R
        else:
            m = P // k
            if m > R:
                m = R
        count = m - current + 1
        res += k * (current + m) * count // 2
        current = m + 1
    return res

def main():
    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
        R_prime = min(R, P)
        if L > R_prime:
            part1 = 0
        else:
            part1 = compute_sum(L, R_prime, P)
        sum_a = (P * (R_prime - L + 1) - part1) + (max(0, R - R_prime) * P)
        print(sum_a)

if __name__ == '__main__':
    main()