#include <bits/stdc++.h>

using namespace std;

long long P, a[6], b[6], c[6], ia1, L, B;

long long inv(long long a, long long b = P){
    return 1 < a ? b - (__int128)inv(b % a, a) * b / a : 1;
}

int check(long long x) {
    x = (__int128)(x + c[1] - L + P) * ia1 % P;
    if (!x) return 0;
    long long sq = sqrt(x), nw = x % sq;
    for (int i = 1; i <= 5; ++i) {
        if (((__int128)x * a[i] + (x % b[i] + 1) * nw) % P != c[i]) return 0;
        nw = (__int128)nw * x % sq;
    }
    printf("%lld\n", x);
    return 1;
}

pair<long long, int> o[1000005];

void calc(long long x, long long y, long long z) {
    z = (z - (__int128)(x - L) * y % P + P) % P;
    int r = 0;
    for (int i = 0; i < B; ++i) o[r++] = {(__int128)i * y % P, i};
    sort(o, o + r);
    o[r++] = {P + 5, 0};
    long long Y = (__int128)y * B % P, mul = (z - (__int128)Y * (B - 1) % P + P) % P;
    for (int i = B - 1; ; --i) {
        long long ctr = mul, tl = ctr - L, tr = ctr;
        if (tl < 0) tl += P;
        if (tl <= tr) {
            for (pair<long long, int> *j = lower_bound(o, o + r, make_pair(tl, 0)); j -> first <= tr; ++j) {
                if (check(i * B + j -> second)) return;
            }
        } else {
            for (pair<long long, int> *j = lower_bound(o, o + r, make_pair(tl, 0)); j != o + r; ++j) {
                if (check(i * B + j -> second)) return;
            }
            for (pair<long long, int> *j = 0; j -> first <= tr; ++j) {
                if (check(i * B + j -> second)) return;
            }
        }
        ((mul += Y) >= P) && (mul -= P);
    }
}

signed main() {
    int T; scanf("%d", &T);
    while (T--) {
        scanf("%*d%lld", &P), L = 0;
        for (int i = 1; i <= 5; ++i) {
            scanf("%lld%lld%lld", &a[i], &b[i], &c[i]);
            L = max(L, b[i]);
        }
        L *= 1000000000, B = sqrt(L) + 5;
        ia1 = inv(a[1]);
        calc(c[1], (__int128)a[2] * ia1 % P, c[2]);
    }
    return 0;
}