#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;
    // cout << range << endl;
    vector<ll> pre(range);
    pre[0] = 0;
    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];
        // 0 1 2 3 4 5
        // 0 1 2 3 
        // cout << "up : " << up << " " << ans << endl;
        return ans;
    };
    // cout << range << endl;
    // cout << pre.back() << endl;
    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();
}