#include <iostream>
#include <math.h>
#include <vector>
#include <functional>
#include <stdlib.h>
using namespace std;

using ll = long long;

ll gcd(ll i , ll j){
    return j == 0 ? i : gcd(j , i % j);
}

void slove(){
    ll x , n;
    cin >> x >> n;
    ll range = 1 << 21;
    vector<int> pre(range);
    pre[0] = 1;
    for (ll i = 1 ; i < pre.size() ; i++){
        pre[i] = pre[i - 1];

        ll tmp = i * x;
        tmp = (tmp + x) - (tmp ^ x);
        if (gcd(tmp , x) != 1) pre[i]++;
    
    }

    function<ll(ll)> cal = [&](ll up){
        ll ans = 0;
        ans = (up / range) * pre.back();
        ans += pre[up % range];
        return ans;
    };

    while(n--){
        ll l , r;
        cin >> l >> r;
        ll res = cal(r) - cal(l - 1);
        cout << res << "\n";
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    slove();
}