#include<bits/stdc++.h>
using namespace std;
const int N=1919810;
typedef long long ll;
typedef pair<ll,ll> PII;
ll n,m,k,p;
ll a[N],b[N];
char s[N];
ll cnt[N];
int num[N];


void print(ll x){
    cout<<(x%p+p)%p<<" ";

}

void __(){
    ll a,b,c,d;
    scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
    if((a+b)%p!=(c+d)%p){
        puts("-1");
        return;
    }
    ll res=(a+b)%p;
    int ans=100;
    ll x=a;
    if(a==c&&b==d){
        puts("0");
        return;
    }
    for(int i=1;i<=50;i++){ 
        x*=2;
        x%=p;
        if((x-c)%res==0){
            // cout<<x-c<<" "<<res<<endl;
            ans=min(ans,i);
        }
       
    }
    x=b;
    for(int i=1;i<=50;i++){
        x*=2;
        x%=p;
        if((x-d)%res==0){
            ans=min(ans,i);
        }
        
    }
    printf("%d\n",ans);
}


int main(){
    int _=1;
    cin>>p;
    cin>>_;
    while(_--){
        __();
    }
}