use std::io::{Read,stdin};

fn main() {
    let mut buf = String::new();
    stdin().read_to_string(&mut buf).unwrap();
    let mut tok = buf.split_whitespace();
    let mut get = || tok.next().unwrap();
    macro_rules! get {
        ($t:ty) => (get().parse::<$t>().unwrap());
        () => (get!(i64));
    }
    
    let p = get!();
    let q = get!();
    for _ in 0..q {
        let li = get!();
        let ri = get!();
        if p < li {
            let ans = (ri - li + 1) * p;
            println!("{}", ans);
        } else {
            let mut ans = 0;
            for i in li..=ri {
                ans += p % i;
            }
            println!("{}", ans);
        }
        
    }

}