#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define sfor(i,j,k) for(register int i=j;i<=k;++i)
#define dfor(i,j,k) for(register int i=k;i>=j;--i)
inline long long read(){
    register long long x = 0, t = 1;
    register char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            t=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*t;
}
int main()
{
long long p=read(),n=read(),a,b,c,d;
sfor(i,1,n)
  {long long a=read(),b=read(),c=read(),d=read();
   long long e=b,f=a;
   if((a+b)%p!=(c+d)%p) {cout<<-1<<endl;continue;}
   int now=0,mow=0;
   while(a!=c)
     {
      b=(b-a+p)%p;
	  a=2*a%p;
      now++;
	 }
   while(e!=f)
     {f=(f-e+p)%p;
	  e=2*e%p;
      mow++;
	 }
   //cout<<now<<" "<<mow<<endl;
   cout<<min(mow,now)<<endl;
  }
}
/*
5 10
2 1 3 0
2 1 4 4
1 3 4 0
0 2 0 4
3 3 1 2
0 1 0 1
0 3 0 3
0 1 0 1
1 2 4 4
1 0 1 1
*/
/*
          ◢■◤
    ◢■■■◤     ◥◣
  ◢■■■■◣       ◥◣
  ◥■■◤◥◣         ■
    ◥◤    ◥◣       ■
      ◢◣    ◥◣   ◢
    ◢◤◥◣    ◥■◤
  ◢◤    ◥■■■■◣
◢◤                ◥◣
*/
//啊啊啊，为什么这么多bug!!!
//我才发现呢，人家Debug是写代码找bug
//感情我是写bug找代码呀
//priority_queue<int> q ;  //大根堆 堆顶最大
//priority_queue<int, vector<int>, greater<int> > q;  //小根堆
//He He He==hai hai hai
//你就是个锑棣
//又双叒叕
//ruo4zhuo2
//聪明人绝不能支持世界  ————鲁迅
//
//知识就是力量，法国是培根的 ————ZY
//
//我是一个经常笑的人，但我不是一个经常开心的人==我微笑不代表我快乐——ZY
//
//给你讲个笑话吧...
//
//话说当年我读二年级时与一个三年级的
//
//人吵架了，于是我叫来了我六年级的哥
//
//哥，他就叫来了他初一的哥哥；我又叫
//
//来了我初三的表哥，他却叫来了他高一
//
//的表哥,还好我表哥学习了田忌赛马这
//
//篇文章，最后由我来对战那个高一的...
//
//秦时明月汉时关
//
//万里长征人未还
//
//但使龙城飞将在
//
//轻舟已过万重山  __NB
//
//爷娘闻女来，出郭相扶将
//
//听君一席话，自挂东南枝
//
//419
//
//已递交
//
//300
//
//已通过
//
//2022.9.17 11：15
//
//# 月夜忆舍弟——子美
//
//戍鼓断人行，边秋一雁声
//
//露从今夜白，月是故乡明
//
//有弟皆分散，无家问死生
//
//寄书长不达，况乃未休兵
//
//壬辰虎年秋日抄————王子美
//
//[https://www.luogu.com.cn/problem/P8079](https://www.luogu.com.cn/problem/P8079)王浚懿 请问你会回溯吗？
//
//对了，每年的五月三十一日是国际禁烟日呢......
//
//黑化肥发挥飞花会挥发会发灰，灰化肥发黑挥发会发挥会飞花
//
//We are lying dragon and chicken.
//
//我们是正在撒谎的龙龙和鸡鸡 (我们是卧龙凤雏。。。）——括号翻译2022.11.19记
//
//冯晨曰：“你自己去看撒...”
//
//我裤子怎么湿漉漉的呀————嘉嘉
//
//这水怎么酸咪咪的呀————臻臻
//
//1：将自己的程序与数据放到同一目录中，这个目录最好只有英文,假设放在c:\aa
//
//2:将自己的程序写成文件输入输出，其中输出文件不要与标准答案文件同名了，假设你的输出为water1.ans,标准答案文件为water1.out
//
//文件输入输出，形如下
//freopen("water1.in","r",stdin);
//freopen("water1.ans","w",stdout);
//
//3:使用组合键ctrl+r，输入cmd,进入dos系统
//
//4:运行cd \
//   进入c盘根目录
//5:运行 cd aa
//  进入aa子目录
//
//6:运行fc water1.out water1.ans
//   对比这两个文件有什么不同
//
//JJYY曰：“”多刺激丫，万一以后能付河呢“”
//
//时代在召唤，菌菌在摆烂
//
//《马其顿大战大汉铁骑》--我有长枪，你过不来
//
//kirka.io??
//
//2022.11.4 LKD永别...
//
//学生永远比老师要强，学生比老师强，社会才会进步--
//王浚懿，请问你会欧拉定理吗？
//听取WA声一片
//青草池塘处处WA
//你就像桌上那份时事报,
//当时读新鲜，以后读怀念
//悲欢越来越远,
//可还是会小心翼翼地折好，安放
//https://www.luogu.com.cn/paste/zejsmuci摸？
//https://www.luogu.com.cn/paste/d1p4zttj
//馬樂我铥雷楼谋
//https://www.luogu.com.cn/user/706859
//https://csacademy.com/app/graph_editor/
//https://www.luogu.com.cn/discuss/567986?page=6摸？
//开数组又不要钱的，你开那么小干什么嘞————ZY
//做任何事，要掌握底层逻辑————ZY
//话说刚刚屏幕上落了一只苍蝇，然后我就习惯性的用鼠标去点它，结果发现点不掉（0v0)
//LJQ：糊题，时间有限，大(zhang)胆(kou)猜(jiu)想(lai)