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

#define int long long  

#define uint unsigned long long

constexpr uint mod = (1ull << 61) - 1;

mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<uint> dist(mod / 2, mod - 1);
const uint base = dist(rnd);

static inline uint add(uint a, uint b) {
    a += b;
    if (a >= mod) {
        a -= mod;
    }
    return a;
}
static inline uint mul(uint a, uint b) {
    __uint128_t c = __uint128_t(a) * b;
    return add(c >> 61, c & mod);
}

vector<int> power;
void init(int n) {
    power.resize(n);
    power[0] = 1;
    for (int i = 1; i < n; i++) {
        power[i] = mul(power[i - 1], base);
    }
}
vector<uint> build(const vector<int> &s) {
    int n = s.size() - 1;
    vector<uint> hashed(n + 1);
    for (int i = 1; i <= n; i++) {
        hashed[i] = add(mul(hashed[i - 1], base), s[i]);
    }
    return hashed;
}

uint query(const vector<uint> &s, int l, int r) {
    return add(s[r], mod - mul(s[l - 1], power[r - l + 1]));
}

uint merge(uint h1, uint h2, int len2) {
    return add(mul(h1, power[len2]), h2);
}

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 f = 1;
    int b = 0;
    int lst = 0;
    while (t.size() < (int)1e7) {
    	if (gcd((f * x) ^ x, x) == 1) {
    		if (b == 0) {
    			b = f;
    		} else {
    			t.push_back(f - lst);
    		}
    		lst = f;
    	}
    	f++;
    }

    init(1e7 + 10);
    auto hash = build(t);

    int len = 0;
    for (int i = 5000000; i >= 2; i -= 2) {
    	if (query(hash, 1, i) == query(hash, i + 1, 2 * i)) {
    		len = i;
    		break;
    	}
	}
    for (int i = 1; i < len; i++) {
    	t[i] += t[i - 1];
    }
    int T = t[len - 1];

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

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

    	int l = -1, r = len;
    	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;
}