#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
        {   
            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;
}