#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 zz = 1;//区间长度
	int pre = -1; 
	for(int i = 1;i <= 1e8;i ++){
		int z = (i * x) ^ x;
		int z1 = __gcd(z,x);
		if(z1 == x){
			if(pre == i - 1){
				zz = i - 1;
				break;
			}
			pre = i;
		}
	}
	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<n;i++){
		int l,r;
		scanf("%lld%lld",&l,&r);
		int ans=0;
		//先求 L 左边有几个 1;
		int lans=0;
		lans=(l-1)/zz*s[zz];
		int ls=(l-1)%zz;
		lans += s[ls];
		
		//在求 R 左边有几个 1;
		int rans=0;
		rans=(r)/zz*s[zz];
		int rs=(r)%zz;
		rans += s[rs];	
		ans = rans - lans;
		
		cout<<ans<<'\n';
	}
	
}

signed main(){

    int T;
    T = 1;
//    cin>>T;
    while(T --){
        solve();
    }
}