#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,len = 0;
	vector<int> res1;
	while(y > 0) {
		res1.push_back(y & 1);
		y /= 2;
		len ++;
	}
	int zz = 0;
	for(int i = 2;i <= 10000000;i ++){
		int k = i * x;
		vector<int> res;
		for(int j = 0;j < len;j ++){
			int q = (k >> j) & 1;
			res.push_back(q);
		}
		int p = 0;
		for(int j = 0;j < len;j ++){
			if(res1[j] != res[j]) p = 1;
		}
		if(p == 0){
			zz = i - 1;
			break ;
		}
	}
	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;
	for(int i = 1;i <= n;i ++){
		int l,r;
		cin >>l>>r;
		l--,r--;
		int sum = 0;
		int L = l/t + 1;
		int R = r/t;
		int ll = 0;
		if(l%t==0) ll = 0;
		else ll = s[l%t];
		if(L>R){
			sum = s[r%t] - ll;
		}else{
			sum = (R-L) * s[t-1] + s[t-1] - ll + s[r%t];
		}
		cout<<sum<<'\n';
	}	
	
}

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