#include <iostream>
using namespace std;
 
typedef long long ll;
ll phi(ll n) {
    ll result = n;
    for (ll p = 2; p * p <= n; ++p) {
        if (n % p == 0) {
            while (n % p == 0) n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    ll l, r, i = 2, n, d;
    int mod, t;
    cin >> mod >> t;
 
    while (t--) {
        cin >> l >> r;
        n = 0;
        for (; l; l >>= 1, r <<= 1) {
            if (l % 2) {
                n += r;
            }
        }
        cout << phi(n) % mod << "\n";
    }
    return 0;
}
 

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKdHlwZWRlZiBsb25nIGxvbmcgbGw7CmxsIHBoaShsbCBuKSB7CiAgICBsbCByZXN1bHQgPSBuOwogICAgZm9yIChsbCBwID0gMjsgcCAqIHAgPD0gbjsgKytwKSB7CiAgICAgICAgaWYgKG4gJSBwID09IDApIHsKICAgICAgICAgICAgd2hpbGUgKG4gJSBwID09IDApIG4gLz0gcDsKICAgICAgICAgICAgcmVzdWx0IC09IHJlc3VsdCAvIHA7CiAgICAgICAgfQogICAgfQogICAgaWYgKG4gPiAxKSByZXN1bHQgLT0gcmVzdWx0IC8gbjsKICAgIHJldHVybiByZXN1bHQ7Cn0KaW50IG1haW4oKSB7CiAgICBpb3M6OnN5bmNfd2l0aF9zdGRpbygwKTsKICAgIGNpbi50aWUoMCk7CiAgICBjb3V0LnRpZSgwKTsKCiAgICBsbCBsLCByLCBpID0gMiwgbiwgZDsKICAgIGludCBtb2QsIHQ7CiAgICBjaW4gPj4gbW9kID4+IHQ7CgogICAgd2hpbGUgKHQtLSkgewogICAgICAgIGNpbiA+PiBsID4+IHI7CiAgICAgICAgbiA9IDA7CiAgICAgICAgZm9yICg7IGw7IGwgPj49IDEsIHIgPDw9IDEpIHsKICAgICAgICAgICAgaWYgKGwgJSAyKSB7CiAgICAgICAgICAgICAgICBuICs9IHI7CiAgICAgICAgICAgIH0KICAgICAgICB9CiAgICAgICAgY291dCA8PCBwaGkobikgJSBtb2QgPDwgIlxuIjsKICAgIH0KICAgIHJldHVybiAwOwp9Cg==

OTk4MjQ0MzUzCjMKMSAyCjIgNQo1IDcK

998244353
3
1 2
2 5
5 7