#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define SZ(x) ((int)(x).size())
#define debug(a) cout<<#a<<":"<<a<<endl
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,b,a) for(int i=b;i>=a;i--)
constexpr int N=1000010;
constexpr int INF=2e9;
constexpr ll LLF=2e18;
constexpr ll mod=998244353;
constexpr int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
ll powmod(ll a,ll b,ll mod=mod) {ll res=1;a%=mod;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll inv(ll a){return powmod(a,mod-2);}
ll n,x,l,r,cnt[N];
void solve() {
	cin>>x>>n;
	ll m=1;
	while(m<x) m*=2;
	rep(i,1,m) {
		cnt[i]=cnt[i-1];
		if(__gcd((x*i)^x,x)==1) cnt[i]++;
	}
	rep(i,1,n){
		cin>>l>>r;l--;
		auto ansl=cnt[m]*(l/m)+cnt[l%m];
		auto ansr=cnt[m]*(r/m)+cnt[r%m];
		cout<<(ansr-ansl)<<"\n";
	}
}
int main() {
	ios::sync_with_stdio(false);cin.tie(nullptr);
	// cout << fixed << setprecision(10);
	//	int testcase;cin>>testcase;rep(_,1,testcase){
	solve();
	//	}
	return 0;	
}