include

using namespace std;

define SZ(X) ((int)(X).size())

define ALL(X) (X).begin(), (X).end()

define REP(I, N) for (int I = 0; I < (N); ++I)

define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)

define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)

define MP make_pair

define PB push_back

define F first

define S second

typedef long long LL;

int MOD, root, half, hv; const int SIZE = 1e6 + 10; vector> pp;

LL mypow(LL x, LL y){ LL res = 1; while(y){ if(y & 1) res = res * x % MOD; y >>= 1; x = x * x % MOD; } return res; }

int find_root(int P){ if(P == 2) return 1; vector fac; for(int i = 2; i * i <= P - 1; i++){ if((P - 1) % i == 0) fac.PB(i), fac.PB(P / i); } int now = 2; while(1){ bool err=0; REP(i, SZ(fac)){ if(mypow(now, fac[i]) == 1){ err = 1; break; } } if(!err) break; now++; } return now; }

void pre(int P){ root = find_root(P); int now = 1; pp.clear(); pp.PB(MP(1, 0)); for(int i = 1; i < P - 1 && i <= 1000000; i++){ now = (LL)now * root % P; pp.PB(MP(now, i)); half = i; hv = now; } hv = mypow(hv, MOD - 2); sort(ALL(pp)); }

int get_id(int x){ int ans = 0, it; while(1){ it = lower_bound(ALL(pp), MP(x, 0)) - pp.begin(); if(it != SZ(pp) && pp[it].F == x) break; ans += half; x = (LL)x * hv % MOD; } return pp[it].S + ans; }

struct gcd_t {LL x, y, z;}; gcd_t gcd(LL a, LL b) { if(b==0) return (gcd_t){1, 0, a}; gcd_t t = gcd(b, a % b); return (gcd_t){t.y, t.x - t.y * (a / b), t.z}; }

int main(){ CASET{ DRII(P, N); MOD = P; pre(P); while(N--){ DRII(A, B); DRII(C, D); if(A < B){ swap(A, B); swap(C, D); } if(C % P == 0 && D % P == 0){ printf("%d\n", A + B); } else if(C % P == 0 || D % P == 0) puts("wala"); else{ C %= P; D %= P; if(P == 2){ printf("%d\n", A + B); continue; } C = get_id(C); D = get_id(D); if(C == 0 && D == 0){ printf("%d\n", A + B); continue; } else if(C == 0){ int gg = __gcd(D, P - 1); printf("%lld\n", A + (LL)B * (P - 1) / gg); continue; } else if(D == 0){ int gg = __gcd(C, P - 1); printf("%lld\n", B + (LL)A * (P - 1) / gg); continue; } int M = P - 1;{ int ha = __gcd(C, __gcd(D, M)); C /= ha; D /= ha; M /= ha; } int gg1 = __gcd(D, M); int M2 = M / gg1; LL now1 = gg1 / __gcd(gg1, C); gcd_t ker = gcd(D, M); while(ker.x < 0) ker.x += M2; LL now2 = C * now1 / ker.z % M2 * ker.x % M2; D = now1; C = now2; if(now2 == 0) now2 = M2; LL mi = A * now1 + B * now2; while((LL)A * (now1 + D) < mi){ now1 += D; now2 += C; if(now2 > M2) now2 -= M2; mi = min(mi, A * now1 + B * now2); } cout << mi << endl; } } } return 0; }