#include<bits/stdc++.h>
using namespace std;
int qpow(int a,int b,int mod)
{
	if(b==0) return 1;
	int g=qpow(a,b/2,mod);
	g=1ll*g*g%mod;
	if(b&1) g=1ll*g*a%mod;
	return g;
}
int p,q;
typedef long long ll;
int main()
{
	cin>>p>>q;
	while(q--)
	{
		int a,b,c,d;
		cin>>a>>b>>c>>d;
		if((a+b)%p!=(c+d)%p)
		{
			cout<<"-1\n";
			continue ;
		}
		int s=qpow((a+b)%p,p-2,p);
		a=1ll*a*s%p;
		c=1ll*c*s%p;
		int ans=0;
		// cerr<<"???"<<a<<" "<<c<<"\n";
		for(;;ans++)
		{
			ll wl=(a*(1ll<<ans))-(1ll<<ans)+1,wr=a*(1ll<<ans);
			ll cc=c+p*((wl-c+p-1)/p);
			// cerr<<wl<<" "<<cc<<" "<<wr<<"\n";
			if(wl<=cc&&cc<=wr) break ;
			// if(wr/p-wl/p>1) break ;
			// if(wr/p==wl/p)
			// {
			// 	wl%=p,wr%=p;
			// 	if(c>=wl&&c<=wr) break ;
			// }
			// else
			// {
			// 	wl%=p,wr%=p;
			// 	if(c>=wl||c<=wr) break ;
			// }
		}
		cout<<ans<<"\n";
	}
}