#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,num = 0;
while(y){
num ++;
y /= 2;
}
int zz = pow(2,num);
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;
// cout<<"zz "<<zz<<endl;
// for(int i = 1;i <= zz;i ++) cout<<s[i]<<" ";
// cout<<endl;
for(int i = 1;i <= n;i ++){
int l,r;
cin >>l>>r;
int sum = 0;
int k = r - l + 1;
sum += k / zz * s[zz];
r -= k / zz * zz;
if(r < l){
cout<<sum<<endl;
continue;
}
int fl = l - l / zz * zz,fr = r - r / zz * zz;
if(l % zz == 0) fl = zz;
if(r % zz == 0) fr = zz;
if(fr >= fl){
if(fl != 0) sum += s[fr] - s[fl - 1];
}
else{
sum += s[zz] - s[fl - 1];
sum += s[fr];
}
// cout<<l<<" "<<r<<endl;
// cout<<fl<<" "<<fr<<endl;
cout<<sum<<endl;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
T = 1;
// cin>>T;
while(T --){
solve();
}
}#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,num = 0;
while(y){
num ++;
y /= 2;
}
int zz = pow(2,num);
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;
// cout<<"zz "<<zz<<endl;
// for(int i = 1;i <= zz;i ++) cout<<s[i]<<" ";
// cout<<endl;
for(int i = 1;i <= n;i ++){
int l,r;
cin >>l>>r;
int sum = 0;
int k = r - l + 1;
sum += k / zz * s[zz];
r -= k / zz * zz;
if(r < l){
cout<<sum<<endl;
continue;
}
int fl = l - l / zz * zz,fr = r - r / zz * zz;
if(l % zz == 0) fl = zz;
if(r % zz == 0) fr = zz;
if(fr >= fl){
if(fl != 0) sum += s[fr] - s[fl - 1];
}
else{
sum += s[zz] - s[fl - 1];
sum += s[fr];
}
// cout<<l<<" "<<r<<endl;
// cout<<fl<<" "<<fr<<endl;
cout<<sum<<endl;
}
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int T;
T = 1;
// cin>>T;
while(T --){
solve();
}
}