#include <bits/stdc++.h>

#define File(a) freopen(a ".in", "r", stdin), freopen(a ".out", "w", stdout)

using ll = long long;

int pow(int a, int b, int ans = 1);

int p, T;

int main() {
  scanf("%d %d", &p, &T);
  while (T--) {
    int a, b, c, d;
    scanf("%d %d %d %d", &a, &b, &c, &d);
    if ((a + b) % p != (c + d) % p) {
      puts("-1");
      continue;
    }
    int s = pow(a + b, p - 2);
    a = 1ll * a * s % p, b = 1ll * b * s % p;
    c = 1ll * c * s % p, d = 1ll * d * s % p;
    for (int k = 0; k <= 30; ++k) {
      ll L = ((ll)(a - 1) << k), R = (ll)a << k;
      L = L + p - c, R = R + p - c;
      if ((R / p) != (L / p)) {
        printf("%d\n", k);
        break;
      }
    }
  }
  return 0;
}

int pow(int a, int b, int ans) {
  while (b) {
    if (b & 1) ans = 1ll * ans * a % p;
    a = 1ll * a * a % p;
    b >>= 1;
  }
  return ans;
}