#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

//ax + by = d，且|x|+|y|最小，其中d=gcd(a,b)

//即使a, b在int范围内，x和y也有可能超过int范围

void exgcd(ll a, ll b, ll &d, ll &x, ll &y)

{

    if (!b){ d = a; x = ; y = ;}

    else{ exgcd(b, a % b, d, y, x); y -= x * (a / b);}

}

//计算模n下a的逆。如果不存在逆，返回-1

//ax=1(mod n)

ll inv(ll a, ll n)

{

    ll d, x, y;

    exgcd(a, n, d, x, y);

    return d ==  ? (x + n) % n : -;

}

inline ll bsgs(ll a, ll b, ll p) {

    a %= p;

    b %= p;

    std::map<ll, ll> map;

    ll m = ceil(sqrt(p)), t = ;

    for (int i = ; i < m; i++) {

        if (!map.count(t)) map[t] = i;

        t = t * a % p;

    }

    ll k = inv(t, p), w = b;

    for (int i = ; i < m; i++) {

        if (map.count(w)) return i * m + map[w];

        w = w * k % p;

    }

    return -;

}

inline ll solve(ll p, ll a, ll b, ll x1, ll t) {

    if (t == x1) return ;

    else if (a == ) return b == t ?  : -;

    else if (a == ) {

        if (!b) return -;

        return ((((t - x1) % p + p) % p) * inv(b, p) % p) + ;

    } else {

        ll q = inv( - a + p, p);

        ll d = (((t - b * q) % p + p) % p) * inv(((x1 - b * q) % p + p) % p, p);

        ll ans = bsgs(a, d, p);

        if (ans == -) return -;

        else return ans + ;

    }

}

int main() {

    int T;

    scanf("%d", &T);

    while (T--) {

        int p, a, b, x1, t;

        scanf("%d %d %d %d %d", &p, &a, &b, &x1, &t);

        printf("%lld\n", solve(p, a, b, x1, t));

    }

}