#include <bits/stdc++.h>
#include <iostream>
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define i128 _int128
#define fi first
#define se second 
#define pb push_back
#define endl '\n'
#define int long long

const ll INF=0x3f3f3f3f;
const int N=2e5+9,M=1e9+9;
const ll mod=998244353;

int read(){
	int s=0,w=1;
	char c=getchar();
	while(!isdigit(c)) (c=='-')?w=-1:w=1,c=getchar();
	while(isdigit(c)) s=(s<<1)+(s<<3)+(c^48),c=getchar();
	return s*w;
}

int qpow(int a,int b){
    a%=mod;
    int res=1;
    while(b){
        if(b&1){res=(res*a)%mod;}
        a=(a*a)%mod;
        b>>=1;
    }
    return res%mod;
}

int gcd(int a,int b){
    if(b==0) return a;
    else return gcd(b,a%b);
}

// int inverse(int a){
//     a%=mod;
// 	return qpow(fac[a%mod],mod-2)%mod;
// }

// int C(int n,int r){
//     n%=mod,r%=mod;
//     if(r>n)return 0;
//     return ((fac[n%mod]*inverse(r))%mod*inverse(n-r))%mod;
// }

// int Lucas(int n,int r){
//     if(r==0)return 1;
//     return C(n%mod,r%mod)%mod*Lucas(n/mod,r/mod)%mod;
// }

int x,n,mini_sum,l,r,ans;
map<int,int> res;

void solve(){
    cin>>x>>n;int p=1;ans=0;
    while(p<x)p*=2;
    int fid=0,lid=0;
    for(int i=0;i<=p;++i){
        if(gcd(((i*x)^x),x)==1){
            //cout<<i<<endl;
            res[i]=1;
            mini_sum++;
            if(fid==0)fid=i;
            lid=i;                
        }
    }
    //cout<<fid<<' '<<lid<<endl;
    while(n--){
        cin>>l>>r;
        if(!x&1)ans=0;
        else{
            ans=0;
            while(l%p!=fid&&l<r){
                if(gcd((l*x)^x,x)==1){
                    ans++;//cout<<l<<endl;
                }
                l++;
            }
            while(r%p!=lid&&r>=l){
                if(gcd((r*x)^x,x)==1){
                    ans++;//cout<<r<<endl;
                }
                r--;
            }
            // cout<<l+(lid-fid)<<' '<<r<<endl;
            // cout<<ans<<endl;
            if(l+(lid-fid)<=r){
                ans+=((r-(l+(lid-fid)))/p+1)*mini_sum;
            }
            cout<<ans<<endl;
        }

    }
    
}
 
 
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
    int _=1;
    // fac[0]=1;
    // for(int i=1;i<=N-9;++i)fac[i]=(fac[i-1]*i)%mod;
    //cin>>_;
    
    while(_--)solve();
 
    return 0;
}