#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 <= 100000000;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();
}
}