#include <bits/stdc++.h>  
using namespace std;  

#define int long long  

signed main() {  
    ios::sync_with_stdio(false);
    cin.tie(nullptr);  

    int x, n;
    cin >> x >> n;

    if (x % 2 == 0) {
    	while (n--) {
    		int l, r;
    		cin >> l >> r;
    		cout << 0 << "\n";
    	}
    	return 0;
    }

    if (x == 1) {
    	while (n--) {
    		int l, r;
    		cin >> l >> r;
    		cout << r - l + 1 << "\n";
    	}
    	return 0;
    }

    vector<int> t;
    int b = 0;
    int f = 1;

    int len = 0;

    auto check = [&](int k) {
    	vector<int> tt;
    	int ff = 1, bb = 0;
    	while (tt.size() < k) {
	    	if (gcd((ff * x) ^ x, x) == 1) {
	    		if (bb == 0) {
	    			bb = ff;
	    		} else {
	    			tt.push_back(ff - bb);
	    		}
	    	}
	    	ff++;
	    }
	    int T = tt.back();
	    for (auto q : tt) {
	    	q += bb;
	    	if (gcd(((q + T) * x) ^ x, x) != 1) {
	    		return false;
	    	}
	    }
	    return true;
    };

    for (int i = x - 1; true; i += 2) {
    	if (check(i)) {
    		len = i;
    		break;
    	}
    }

    while (t.size() < len) {
    	if (gcd((f * x) ^ x, x) == 1) {
    		if (b == 0) {
    			b = f;
    		} else {
    			t.push_back(f - b);
    		}
    	}
    	f++;
    }

    int T = t.back();

    auto calc = [&](int a) {
    	if (a < b) {
    		return 0LL;
    	}

    	a -= b;
    	int ret = 1 + a / T * t.size();
    	a %= T;

    	int l = -1, r = t.size();
    	while (l + 1 != r) {
    		int m = (l + r) / 2;
    		if (t[m] <= a) {
    			l = m;
    		} else {
    			r = m;
    		}
    	}
		ret += l + 1;	
    	return ret;
    };

    while (n--) {
    	int l, r;
    	cin >> l >> r;
    	cout << calc(r) - calc(l - 1) << "\n";
    }

    return 0;
}