abc270G

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&... values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
using ll = long long;
using pii = pair<int, int>;

int t;
int p, a, b, s, g;

ll fast_pow(ll base, ll x, ll p)
{
    ll ret = 1;
    ll pow = base;
    while (x) {
        if (x & 0x01)
            ret = ret * pow % p;
        x = x / 2;
        pow = pow * pow % p;
    }
    return ret;
}

ll solve()
{
    // dbg(p, a, b, s, g);
    if (s == g)
        return 0;
    if (a == 0)
        return (b == g ? 1 : -1);
    ll m = sqrt(p);
    ll inv_a = fast_pow(a, p - 2, p);
    // dbg(m, inv_a);
    unordered_map<ll, ll> small_step;
    ll c = ((p - inv_a * b % p) % p + p) % p;
    ll rem = (inv_a * g % p + c) % p;
    // dbg(rem);
    // small_step[s] = 0;
    small_step[g] = 0;
    for (int i = 0; i <= m; ++i) {
        small_step[rem] = i + 1;
        if (small_step.count(s))
            return small_step[s];
        // dbg(small_step[rem], rem);
        rem = (inv_a * rem % p + c) % p;
    }

    c = 0;
    ll aa = 1;
    ll an = fast_pow(a, m, p);
    for (int i = 0; i < m; ++i) {
        c = (aa + c) % p;
        aa = aa * a % p;
    }
    c = c * b % p;
    rem = (an * s % p + c) % p;
    // dbg(rem);

    unordered_map<ll, ll> giant_step;
    for (int i = 0; i <= p / m; ++i) {
        giant_step[rem] = i + 1;
        // dbg(giant_step[rem], rem);
        if (small_step.count(rem))
            return m * (i + 1) + small_step[rem];
        rem = (an * rem % p + c) % p;
    }

    return -1;
}

int main(int argc, char **argv)
{
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d%d%d", &p, &a, &b, &s, &g);
        ll res = solve();
        printf("%lld\n", res);
    }
    return 0;
};