#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int a, b, c, d;
int p;

int ksm(int x, int y) {
	int w = 1;
	for(; y; y >>= 1, x = 1ll * x * x % p)
		if(y & 1)
			w = 1ll * w * x % p;
	return w;
}
void solve() {
	cin >> a >> b >> c >> d;
	if((a + b) % p != (c + d) % p) {
		cout << "-1\n"; return ;
	}
	int inv = ksm((a + b) % p, p - 2);
	a = 1ll * a * inv % p;
	c = 1ll * c * inv % p;
	if(a == 0) a = p;
	for(int i = 0; i < 30; i++) {
		ll l = 1ll * a * (1 << i) - (1 << i) + 1;
		ll r = 1ll * a * (1 << i);
		if(r - l + 1 >= p) {
			cout << i << "\n"; return ;
		}
		if(l % p < r % p && l % p <= c && c <= r % p) {
			cout << i << "\n"; return ;
		}
		if(l % p > r % p && (c >= l % p || c <= r % p)) {
			cout << i << "\n"; return ;
		}
	}
}
int main() {
	ios::sync_with_stdio(0); cin.tie(nullptr);
	cin >> p; int T; cin >> T;
	for(; T; --T) solve();
	return 0;
}