//#include <iostream>
//#include <string>
//#include <string.h>
//#include <vector>
//#include <algorithm>
//#include <cmath>
//#include <set>
//#include <random>
//#include <cstdlib>
//#include <numeric>
//#include <functional>
//#include <queue>
//#include <stdlib.h>
//#include <map>
//using namespace std;
//using ll = long long;
//ll mod = 1e9 + 7;
//
//// 定义dp[i][j] 为i的j祖先中最大值
//// dp[i][j + 1] = max(dp[i][j] , dep[fa[i][j]] - dep[i] + dep[fa[i][j]][j]);
//
//void slove() {
//    int n , q;
//    cin >> n;
//    int lg = log2(n) + 1;
//    vector<vector<int>> edges(n + 1);
//    vector<int> dep(n + 1);
//    vector<vector<int>> fa(n + 1, vector<int>(lg + 1));
//    vector<vector<int>> dp(n + 1, vector<int>(lg + 1));
//    vector<int> dis1(n + 1) ,dis2(n + 1);
//
//    for (int i = 1 , u ,v; i < n; i++) {
//        cin >> u >> v;
//        edges[u].push_back(v);
//        edges[v].push_back(u);
//    }
//
//    function<void(int)> dfs = [&](int i) {
//        for (auto nx : edges[i]) {
//            if (nx == fa[i][0]) continue;
//            fa[nx][0] = i;
//            dep[nx] = dep[i] + 1;
//            dfs(nx);
//
//            int dis = dis1[nx] + 1;
//            if (dis > dis1[i]) {
//                dis2[i] = dis1[i];
//                dis1[i] = dis;
//            }
//            else if (dis > dis2[i]) dis2[i] = dis;
//        }
//    };
//
//    dfs(1);
//
//    for (int j = 1; j <= lg; j++) {
//        for (int i = 1; i <= n; i++)
//            fa[i][j] = fa[fa[i][j - 1]][j - 1];
//    }
//
//    for (int i = 2; i <= n; i++) {
//        dp[i][0] = (dis1[fa[i][0]] == dis1[i] + 1 ? dis2[fa[i][0]] + 1 : dis1[fa[i][0]] + 1);
//    }
//
//    for (int j = 1; j <= lg; j++) {
//        for (int i = 2; i <= n; i++) {
//            dp[i][j] = max(dp[i][j - 1],dep[i] - dep[fa[i][j - 1]] + dp[fa[i][j - 1]][j - 1]);
//        }
//    }
//
//    cin >> q;
//    while (q--) {
//        int v, k;
//        cin >> v >> k;
//
//        int ans = dis1[v];
//        int ptr = v;
//        for (int i = 20; i >= 0; i--) {
//            if (k & (1 << i)) {
//                ans = max(ans, dp[ptr][i] + dep[v] - dep[ptr]);
//                ptr = fa[ptr][i];
//            }
//        }
//
//        cout << ans << ' ';
//    }
//    cout << endl;
//    
//}
//
//
//
//int main() {
//    ios::sync_with_stdio(false);
//    cin.tie(0);
//    cout.tie(0);
//    //freopen("in.txt", "r", stdin);
//    //freopen("out.txt", "w", stdout);
//
//    int cnt = 1;
//    cin >> cnt;
//    while (cnt--) {
//        slove();
//    }
//    return 0;
//}

#include <iostream>
#include <math.h>
#include <vector>
#include <functional>
#include <stdlib.h>
using namespace std;

using ll = long long;

ll gcd(ll i, ll j) {
	return j == 0 ? i : gcd(j, i % j);
}

void slove() {
	ll x, n;
	cin >> x >> n;
	ll range = 1 << 21;
	// cout << range << endl;
	vector<ll> pre(range);
	pre[0] = 0;
	for (ll i = 1; i < pre.size(); i++) {
		pre[i] = pre[i - 1];

		ll tmp = i * x;
		tmp = (tmp + x) - (tmp ^ x);
		if (gcd(tmp, x) == 1) pre[i]++;

	}

	function<ll(ll)> cal = [&](ll up) {
		ll ans = 0;
		ans = (up / range) * pre.back();
		ans += pre[up % range];
		// cout << "up : " << up << " " << ans << endl;
		return ans;
	};
	// cout << range << endl;
	// cout << pre.back() << endl;
	while (n--) {
		ll l, r;
		cin >> l >> r;
		ll res = cal(r) - cal(l - 1);
		cout << res << "\n";
	}
}

int main() {
	// ios::sync_with_stdio(false);
	// cin.tie(0);
	// cout.tie(0);

	slove();
}