#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fi first
#define se second

int gcd(int a,int b){
	return b ? gcd(b,a % b) : a;
}

void solve(){
	int x,n;
	cin >>x>>n;
	int zz = x;
	for(int i = 2;i <= x + 10;i ++){
		int z = (i * x) ^ x;
		int z1 = gcd(z,x);
		if(z1 == x){
			x = i;
			break;
		}
	}
	vector<int> s(x + 1);
	for(int i = 1;i <= x;i ++){
		int z = (i * zz) ^ zz;
		int z1 = gcd(z,zz);
		if(z1 == 1){
			s[i] = s[i - 1] + 1;
		}
		else s[i] = s[i - 1];
	}
	for(int i = 1;i <= n;i ++){
		int l,r;
		cin >>l>>r;
		int sum = 0;
		if(l == r){
			l = (l % (x));
			if(l == 0)cout<<s[(x)] - s[x - 1]<<'\n';
			else cout<<s[l] - s[l - 1]<<'\n';
			continue;
		}
		if(l % (x) == 0){
			l ++;
			sum += s[x] - s[x - 1];
		}
		if(r <= l + ((x) - (l % (x)))){
			if(r % (x) != 0)cout<<s[r % (x)] - s[(l % (x)) - 1]<<'\n';
			else cout<<s[x] - s[(l % (x)) - 1]<<'\n';
			continue;
		}
		int z = l % (x);
		int z1 = r % (x);
		r -= r % (x);
		l += ((x) - (l % (x)));
		sum = ((r - l) / (x)) * s[x];
		sum += s[(x)] - s[z - 1];
		sum += s[z1] - s[0];
		cout<<sum<<'\n';
	}
}

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