#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int p, q;
    std::cin >> p >> q;

    auto qpow = [&](int x, int y) {
        int ans = 1;
        while (y) {
            if (y & 1) {
                ans *= x;
                ans %= p;
            }
            x *= x;
            x %= p;
            y /= 2;
        }
        return ans;
    };

    for (int i = 1; i <= q; i++) {
        int base = 2;
        int a, b, c, d;
        std::cin >> a >> b >> c >> d;
        if ((a + b) % p != (c + d) % p) {
            std::cout << -1 << '\n';
            continue;
        }
        int inv = qpow(a + b, p - 2);

        if (a == c && b == d) {
            std::cout << 0 << '\n';
            continue;
        }

        for (int j = 1; j <= 40; j++) {
            int now = a * base % p;
            int cha = (now - c + p) % p;

            int ans = cha * inv % p;

            // std::cout << now << " " << cha << ' ' << ans << '\n';

            if (ans < base) {
                std::cout << j << '\n';
                break;
            }

            base *= 2;
            if(base >= p) {
                std::cout << i << '\n';
                break;
            }
        }
    }
}

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

    int t = 1;
    // std::cin >> t;

    while(t --) {
        solve();
    }
}