import sys
import math

def main():
    input = sys.stdin.read().split()
    ptr = 0
    P = int(input[ptr])
    ptr +=1
    Q = int(input[ptr])
    ptr +=1
    
    queries = []
    for _ in range(Q):
        L = int(input[ptr])
        ptr +=1
        R = int(input[ptr])
        ptr +=1
        queries.append((L, R))
    
    K = int(math.isqrt(P))
    
    for L, R in queries:
        sum_total = 0
        
        # 处理 d <= K 的情况
        d_max = P // L if L != 0 else 0
        for d in range(1, K +1):
            lower = (P // (d +1)) + 1
            upper = P // d
            lower = max(L, lower)
            upper = min(R, upper)
            if lower > upper:
                continue
            count = upper - lower +1
            sum_n = (lower + upper) * count // 2
            sum_total += d * sum_n
        
        # 处理 n <= K 的情况，此时 d = P //n 可能大于 K
        n_start = max(L, 1)
        n_end = min(R, K)
        for n in range(n_start, n_end +1):
            d = P // n
            if d > K:
                sum_total += n * d
        
        # 计算最终结果
        total_mod = P * (R - L +1) - sum_total
        print(total_mod)
    
if __name__ == '__main__':
    main()