#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 = prefix[r % p] - prefix[l % p - 1] + mini_sum * ((r - l) / p);
            // if(r%p!=lid)r=r-r%p;
            // if(l%p!=fid)l+=p-l%p;
            // caseout<<l<<' '<<r;
            // if(l<r)ans+=mini_sum;
            if (l - l % p + 2*p <= r)ans += 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;
}

// 二进制优化多重背包、01、完全背包的混合背包问题
//  void ZeroOnePackage(int i){
//      for(int j=t;j>=w[i];--j){
//          dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
//      }
//      return;
//  }

// void FullPackage(int i){
//     for(int j=w[i];j<=t;++j){
//         dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
//     }
//     return;
// }

// void MuLtiPackage(int i){
//     memcpy(g,dp,sizeof(g));
//     int q[N];
//     for(int j=0;j<w[i];++j){
//         int head=0,tail=-1;
//         for(int k=j;k<=t;k+=w[i]){
//             while(head<=tail&&(k-q[head])/w[i]>c[i])head++;
//             while(head<=tail&&(k-q[tail])/w[i]*v[i]+g[q[tail]]<=g[k])tail--;
//             q[++tail]=k;
//             dp[k]=g[q[head]]+(k-q[head])/w[i]*v[i];
//         }
//     }
//     return;
// }

// void solve(){
// 	s11=read();s12=read();s21=read();s22=read();
//     t=s21*60+s22-s11*60-s12;
//     n=read();
//     for(int i=1;i<=n;++i){w[i]=read();v[i]=read();c[i]=read();}
//     for(int i=1;i<=n;++i){
//         if(c[i]==0)FullPackage(i);
//         if(c[i]==1)ZeroOnePackage(i);
//         if(c[i]>=2)MuLtiPackage(i);
//     }
//     cout<<dp[t]<<endl;

// }

// 牛客多校第8场 A题 枚举数字的倍数求gcd
//  void solve(){
//      int n;cin>>n;int cnt=0;
//      vector<int> vis(N+1);
//      for(int i=0;i<n;++i){
//          int a;cin>>a;
//          vis[a]=1;
//      }
//      for(int i=1;i<=N;++i){
//          int d=0;
//          for(int j=i;j<=N;j+=i){//枚举倍数
//              if(vis[j])d=gcd(d,j);
//          }
//          if(d==i && !vis[d])cnt+=1;//当i所有倍数的gcd就是i,且数列无i，则i可被添加
//      }
//      if(cnt&1)cout<<"dXqwq"<<endl;
//      else cout<<"Haitang"<<endl;
//  }

// P1827 USACO3.4 根据前序和中序求出后序
//  void changePost(string pre,string in){
//      if(pre.empty())return;
//      char root=pre[0];
//      int pos=in.find(root);
//      pre.erase(pre.begin());

//     string lp=pre.substr(0,pos);string rp=pre.substr(pos);
//     string lin=in.substr(0,pos);string rin=in.substr(pos+1);

//     changePost(lp,lin);changePost(rp,rin);
//     cout<<root;
// }

// P3370字符串无错哈希//该题解内还有多重哈希和字典树讲解
//  #include <bits/stdc++.h>
//  using namespace std;

// typedef long long ll;
// typedef long double ld;
// typedef unsigned long long ull;

// #define endl '\n'
// const ull mod=2024080620050421;
// const ull prime=233317;

// ull base=131;
// ull a[10010];
// char s[10010];
// int n,ans=1;

// ull hashe(char s[]){
//     int len=strlen(s);
//     ull res=0;
//     for(int i=0;i<len;++i)res=(res*base+(ull)s[i])%mod+prime;
//         return res;
// }

// void solve(){
//     memset(a,0,sizeof(a));memset(s,' ',sizeof(s));
//     cin>>n;
//     for(int i=1;i<=n;++i){
//         cin>>s;a[i]=hashe(s);
//     }
//     sort(a+1,a+n+1);
//     for(int i=1;i<n;++i){
//         if(a[i]!=a[i+1])ans++;
//     }
//     cout<<ans<<endl;
// }

// int main(){
//     ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

//     int _=1;
//     //cin>>_;
//     while(_--)solve();

//     return 0;
// }

// 牛客多校第六场A题(dfs、树状dp、树状数组)
//  #include<bits/stdc++.h>
//  #define ll long long
//  using namespace std;

// const int maxn=210000;

// vector<pair<int,int> > V[maxn];//树的邻接链表
// int n;
// int p[maxn][2];
// //p[i][0]和p[i][1]分别表示以节点i为根的子树中,所有从i到其叶子节点的路径上0和1的总数
// int dep[maxn];//;dep存储每个节点的深度。
// double f[ maxn];//f[i]用来存储前缀串中0出现过的最大比例
// double g[maxn];

// void dfs(const int x,const int fa){
// 	if(x!=1){
// 		f[x]=max(f[x],(double)p[x][0]/(p[x][0]+p[x][1]));
// 		//每次更新当前节点的前缀串中0出现过的最大比例
// 		//例如，在1->3的路径上，前缀串中0的比例为1，则之后从3起的路径上，f都为1
// 	}
// 	else f[x]=0;

// 	for(auto [y,c]:V[x])if(y!=fa){//对当前节点的子节点进行操作
// 		//y是子节点，c是边上权值
// 		p[y][0]=p[x][0],p[y][1]=p[x][1];p[y][c]++;
// 		//继承父节点的路径，构造前缀01串
// 		dep[y]=dep[x]+1;

// 		f[y]=f[x];
// 		//继承父节点前缀串中0的比例

// 		dfs(y,x);
// 	}
// }
// //dfs后，整个树上每个节点都计算了该路径中0出现过的最大比例f

// void dp(const int x,const int fa){
// 	int sz=0;
// 	if(dep[x]&1) g[x]=1;
// 	else g[x]=0;

// 	for(auto [y,c]:V[x]) if(y!=fa){
// 		dp(y,x);
// //dp执行至叶节点后返回至叶节点的父节点，叶节点高度计1
// //递归至叶节点的过程中将奇数层节点的g置为1，偶数层置为0,方便之后对两人分别取最小/最大值
// 		sz++;//高度更新
// 		if(dep[x]&1)//Grammy
// 		{
// 			g[x]= min(g[x],g[y]);
// 		}
// 		else//Oscar
// 		{
// 			g[x]= max(g[x],g[y]);
// 		}
// //从叶节点的父节点返回至根节点的过程中，更新g[x]的值：
// //奇数层Grammy：x子节点中和其本身中的最小值
// //偶数层Oscar：x子节点中和其本身中的最大值
// 	}
// 	if(sz==0){
// 		g[x]=f[x];
// 	}
// //递归至叶节点后将g置为其f的值，开始执行返回到根节点的过程
// }

// int main(){
// 	ios_base::sync_with_stdio(0);

// 	int Tcase; cin>>Tcase;
// 	while(Tcase--){
// 		cin>>n;
// 		for(int i=1;i<=n;i++){
// 			vector<pair<int,int> >_;
// 			V[i].swap(_);//清空V向量
// 		}
// 		for(int i=1;i<n;i++){
// 			int x,y,c;cin>>x>>y>>c;
// 			V[x].emplace_back(y,c);
// 			V[y].emplace_back(x,c);
// 		}//构建邻接链表
// 		dep[1]=1;p[1][0]=p[1][1]=0;//重设根节点属性
// 		f[1]=0;dfs(1,0);
// 		dp(1,0);
// 		cout<<fixed<<setprecision(12)<<1-g[1]<<endl;

// 	}

// 	return 0;
// }

// 牛客多校第二场C题（dp）//看不懂它状态转移的原理
//  #include <bits/stdc++.h>
//  typedef long long ll;
//  using namespace std;
//  const ll MAXN=1e6+9;
//  int main() {
//      ios::sync_with_stdio(false);cin.tie(nullptr);

//     int n;cin>>n;vector<string> a(2);
//     for(auto &s:a){cin>>s;}
//     vector dp(2,vector(n,vector(2, 0)));
//     //vector<vector<vector<int>>> dp(2, vector<vector<int>>(n, vector<int>(2, 0)));
//     for(int j=0;j<n;j++){
//         for(int i=0;i<2;i++){
//             if(a[i][j]=='R'){
//                 dp[i][j][0]=1;
//             }
//         }
//     }
//     // dp[i][j][0]表示从左边出发，到达j时，步数的最大值
//     // dp[i][j][1]表示从右边出发，到达j时，步数的最大值
//     for(int j=0;j<n;j++){
//         for(int i=0;i<2;i++){
//             if(a[i][j]=='R'&&j>0){//从左边出发
//                 dp[i][j][0]+=max(dp[i][j-1][0],dp[i][j-1][1]);
//             }
//         }
//         for(int i=0;i<2;i++){
//             if(a[i][j]=='R'){//从右边出发
//                 dp[i][j][1]=dp[i^1][j][0]+1;
//     //^1 操作是用来切换玩家的，即 i ^ 1 将会得到另一个玩家的索引（0 或 1）
//             }
//         }
//     }

//     int ans=0;
//     for(int i=0;i<2;i++){
//         for(int j=0;j<n;j++) {
//             for(int k=0;k<2;k++) {
//                 ans=max(ans, dp[i][j][k]);
//             }
//         }
//     }

//     cout<<max(0,ans-1)<<endl;

//     return 0;
// }

// a,b互质，则其最大不能表示出的数是ab-a-b；
//  牛客竞赛语法入门班顺序结构习题1047
//  signed main(){
//  	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);

//   int n,m;cin>>n>>m;
//   cout<<n*m-n-m;

//   return 0;
// }