#include <bits/stdc++.h>
using namespace std;
#define maxn 2000005
#define int long long 
#define endl '\n'

int x,n;
int cir;
int dp[maxn];

int cal(int p){
    int res;
    int k,r;
    k=p/cir;r=p%cir;
    res=dp[cir]*k+dp[r];
    return res;
}

void solve(){
    cin>>x>>n;
    cir=1;
    while(x/cir){
        cir*=2;
    }
    for(int i=1;i<=cir;i++){
        dp[i]=dp[i-1]+(__gcd((i*x)^x,x)==1);
    }
    while(n--){
        int l,r;
        cin>>l>>r;
        cout<<cal(r)-cal(l-1)<<endl;
    }
    return;
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int TT=1;//cin>>TT;
    while(TT--){
        solve();
    }
}