# coding: utf-8

def main():
	d = [None] * pow(10,9)
	P, Q = list(map(int, input().split(' ')))
	l = [list(map(int, input().split(' '))) for _ in range(Q)]
	for L, R in l:
		for i in range(L, R+1):
			if d[i] is None: d[i] = P % i
		print(sum(d[L:R+1]))
main()