#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int mod,Q;
int qpow(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=1LL*ans*a%mod;
		a=1LL*a*a%mod;
		b>>=1;
	}
	return ans;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin>>mod>>Q;
	while(Q--){
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		if((a+b)%mod!=(c+d)%mod){
			cout<<-1<<'\n';
			continue;
		}
		if(a==c){
			cout<<0<<'\n';
			continue;
		}
		int s=(a+b)%mod;
		int invs=qpow(s,mod-2);
		a=1LL*a*invs%mod,c=1LL*c*invs%mod;
		for(int o=1,l=a,r=a,len=1;;++o){
			len<<=1;
			l=(2*l-1+mod)%mod;
			r=2*r%mod;
			if(len>=mod||(l<=r&&c>=l&&c<=r)||(l>r&&(c<=r||c>=l))){
				cout<<o<<'\n';
				break;
			}
		}
	}
	return 0;
}