#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,p;
int qpow(int a,int b){
	int res = 1;
	for( ; b; b >>= 1){
		if(b & 1) res = (res * a) % p;
		a = (a * a) % p;
	}
	return res;
}
int a,b,c,d;
signed main(){
	scanf("%lld %lld",&p,&T);
	while(T--){
		scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
		if((a + b) % p != (c + d) % p){
			printf("-1\n");
			continue;
		}
		int inv = qpow((a + b) % p,p - 2);
		(a *= inv) %= p,(b *= inv) %= p,(c *= inv) %= p,(d *= inv) %= p;
		//a -> c
		int L = a,R = a;
		for(int k = 0; ; k++){
			if(R - L + 1 >= p){
				printf("%lld\n",k);
				break;
			}
			if(L % p <= R % p && L % p <= c && c <= R % p){
				printf("%lld\n",k);
				break;
			}
			if(L % p > R % p && (c >= L % p || c <= R % p)){
				printf("%lld\n",k);
				break;
			}
			L = 2 * L - 1,R = 2 * R;
		}
	}
	return 0;
}