#include <bits/stdc++.h>

using namespace std;
using LL = long long;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  int x, n;
  cin >> x >> n;
  int lim = 1 << (int)ceil(log2(x));
  vector<int> f(n + 1);
  for (int i = 1; i <= lim; i++) {
    f[i] = f[i - 1] + (__gcd<LL>((1ll * i * x) ^ x, x) == 1);
  }
  auto solve = [&](LL n) {
    return (n / lim) * f[lim] + f[n % lim];
  };
  while (n--) {
    LL l, r;
    cin >> l >> r;
    cout << solve(r) - solve(l - 1) << '\n';
  }
  return 0;
}