#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 = 4e6 + 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;
int prefix[N];

void solve(){
    cin>>x>>n;
    int p=1;
    ans=0;
    memset(prefix,0,sizeof(prefix));
    while(p<x)p*=2;
    int fid=0,lid=0;
    for(int i=1;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;
        }
        prefix[i]=prefix[i-1]+res[i];
    }
    // for(int i=1;i<=p;++i){
    //     cout<<i<<'-'<<prefix[i]<<endl;
    // }
    // cout<<fid<<' '<<lid<<endl;
    while(n--){
        cin>>l>>r;
        if(!x&1)ans=0;
        else{
            ans=0;
            int cl=ceil((double)l/p),cr=r/p;
            if(p*cl<=p*cr){
                ans=mini_sum*(cr-cl);
                ans+=prefix[r%p];
            }
            ans+=prefix[min(r,cl*p-1)%p]-prefix[(l-1)%p];
            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;
}