ENV[Z='RUBY_THREAD_VM_STACK_SIZE']||exec({Z=>?5*8},'ruby',$0)
M={0=>0}
def C n;M[n]||=C(-1+x=P/(P/n+1)+1)+(P%n+P%x)*(n-x+1)/2 end
P,q=gets.split.map &:to_i
q.times{l,r=gets.split.map &:to_i;p C(r)-C(l-1)}