#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll n,m,x,pre[1100010];
ll gcd(ll a,ll b)
{
	return (!b)?a:gcd(b,a%b);
}
ll clac(ll num)
{
	ll sum=0,frac=(num+1)/m,las=(num+1)%m;
	sum+=(frac*pre[m-1]);
	if(las)
		sum+=pre[las-1];
	return sum;
}
int main()
{
	ll i,l,r;
	scanf("%lld %lld",&x,&n);
	for(i=30;i>=0;--i)
	{
		if(x&(1ll<<i))
		{
			m=(1ll<<(i+1));
			break;
		}
	}
	for(i=0;i<m;++i)
		pre[i]=(gcd((i*x)^x,x)==1?1:0);
	for(i=1;i<m;++i)
		pre[i]+=pre[i-1];
	for(i=1;i<=n;++i)
	{
		scanf("%lld %lld",&l,&r);
		printf("%lld\n",clac(r)-clac(l-1));
	}
	return 0;
}