#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define endl '\n'
typedef pair<int,int> PII;

void solve(){
	int n,x;
	cin >>x>>n; 
	int y = x,num = 0;
	while(y){
		num ++;
		y /= 2;
	}
	int zz = pow(2,num);
	
	vector<int> s(zz + 1);
	for(int i = 1;i <= zz;i ++){
		int z = (i * x) ^ x;
		int z1 = __gcd(z,x);
		if(z1 == 1){
			s[i] = s[i - 1] + 1;
		}
		else s[i] = s[i - 1];
	}
//	for(int i = 0;i < zz;i++) s[i] = s[i+1];
//	int t = zz;
//	cout<<"zz "<<zz<<endl;
//	for(int i = 1;i <= zz;i ++) cout<<s[i]<<" ";
//	cout<<endl;
	for(int i = 1;i <= n;i ++){
		int l,r;
		cin >>l>>r;
		int sum = 0;
		
		int k = r - l + 1;
		sum += k / zz * s[zz];
		r -= k / zz * zz;
		if(r < l){
			cout<<sum<<endl;
			continue;
		}
		int fl = l - l / zz * zz,fr = r - r / zz * zz;
		if(l % zz == 0) fl = zz;
		if(r % zz == 0) fr = zz;
		if(fr >= fl){
			if(fl != 0) sum += s[fr] - s[fl - 1];
		}
		else{
			sum += s[zz] - s[fl - 1];
			sum += s[fr]; 
		} 
//		cout<<l<<" "<<r<<endl;
//		cout<<fl<<" "<<fr<<endl;
		
		cout<<sum<<endl;
	}	
	
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int T;
    T = 1;
//    cin>>T;
    while(T --){
        solve();
    }
}#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second
#define endl '\n'
typedef pair<int,int> PII;

void solve(){
	int n,x;
	cin >>x>>n; 
	int y = x,num = 0;
	while(y){
		num ++;
		y /= 2;
	}
	int zz = pow(2,num);
	
	vector<int> s(zz + 1);
	for(int i = 1;i <= zz;i ++){
		int z = (i * x) ^ x;
		int z1 = __gcd(z,x);
		if(z1 == 1){
			s[i] = s[i - 1] + 1;
		}
		else s[i] = s[i - 1];
	}
//	for(int i = 0;i < zz;i++) s[i] = s[i+1];
//	int t = zz;
//	cout<<"zz "<<zz<<endl;
//	for(int i = 1;i <= zz;i ++) cout<<s[i]<<" ";
//	cout<<endl;
	for(int i = 1;i <= n;i ++){
		int l,r;
		cin >>l>>r;
		int sum = 0;
		
		int k = r - l + 1;
		sum += k / zz * s[zz];
		r -= k / zz * zz;
		if(r < l){
			cout<<sum<<endl;
			continue;
		}
		int fl = l - l / zz * zz,fr = r - r / zz * zz;
		if(l % zz == 0) fl = zz;
		if(r % zz == 0) fr = zz;
		if(fr >= fl){
			if(fl != 0) sum += s[fr] - s[fl - 1];
		}
		else{
			sum += s[zz] - s[fl - 1];
			sum += s[fr]; 
		} 
//		cout<<l<<" "<<r<<endl;
//		cout<<fl<<" "<<fr<<endl;
		
		cout<<sum<<endl;
	}	
	
}

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

answer.code:73:2: error: stray ‘#’ in program
   73 | }#include<bits/stdc++.h>
      |  ^
answer.code:73:3: error: ‘include’ does not name a type
   73 | }#include<bits/stdc++.h>
      |   ^~~~~~~
answer.code:81:6: error: redefinition of ‘void solve()’
   81 | void solve(){
      |      ^~~~~
answer.code:9:6: note: ‘void solve()’ previously defined here
    9 | void solve(){
      |      ^~~~~
answer.code:135:8: error: redefinition of ‘int main()’
  135 | signed main(){
      |        ^~~~
answer.code:63:8: note: ‘int main()’ previously defined here
   63 | signed main(){
      |        ^~~~