$$x_2 = ax_1+b$$
$$x_3 = ax_2+b = a^2x_1 + ab + b$$
$$x_4 = ax_3+b = a^3x_1 + a^2b + ab + b$$
$$\dots$$

并不难发现：
$$x_i = a^{i-1} x_1 + b\sum\limits_{j=0}^{i-2} a^j$$

把等比数列求和公式套上去：

$$x_i = \Big( a^{i-1} x_1 + b \times \frac{a^{i-1}-1}{a-1} \Big) \bmod p$$

现在相当于要求一个最小的 $i$，使得：

$$a^{i-1} x_1 + b \times \frac{a^{i-1}-1}{a-1} \equiv t \pmod p$$

$$\frac{ a^i x_1 - a^{i-1} x_1 + a^{i-1}b - b }{a-1} \equiv t \pmod p$$

$$a^i x_1 - a^{i-1} x_1 + a^{i-1}b \equiv ta - t + b \pmod p$$

$$a^{i-1} ( ax_1 - x_1 + b ) \equiv ta - t + b \pmod p$$

由于 $p$ 是质数，$ax_1-x_1+b$ 一定有逆元：

$$a^{i-1} \equiv \frac{ta - t + b}{ ax_1 - x_1 + b } \pmod p$$

于是这题就变成了一个裸的 BSGS 板子。

为什么我的式子这么丑啊。不过还是很好推的。

然后有一车 Corner Case：

• $x=t$：第一步就到了。
• $a=0$：第一天是 $x$，后面都是 $b$，判第二天即可。
• $a=1$：不断往后跳 $b$ 步，$x+(i-1)b \equiv t \pmod p$，即 $i \equiv \frac{t-x}{b} +1 \pmod p$。
  • 注意这东西可能 $=0$，这时候要输出 $p$。

然后当上面式子的分母为 $0$ 时也要输出 $-1$。

#include <bits/stdc++.h>
#define int long long
using namespace std;

unordered_map<int, int> mp;

int qmi(int a, int k, int p) {
    int res = 1 % p;
    while (k) {
        if (k & 1) res = res * a % p;
        a = a * a % p, k >>= 1;
    }
    return res;
}
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int BSGS(int a, int b, int p) {
    a %= p, b %= p;
    int T = sqrt(p) + 1; mp.clear();
    int mul = 1, now = 1;
    for (int i = 0; i <= T; i++) {
        if (mul == b) return i;
        if (!mp.count(b * mul % p)) mp[b * mul % p] = i;
        if (i < T) mul = mul * a % p;
    }
    for (int j = 1; j <= T; j++) {
        now = now * mul % p;
        if (mp.count(now)) return j * T - mp[now];
    }
    return -1;
}

int T, p, a, b, x, t;

void solve() {
    scanf("%lld%lld%lld%lld%lld", &p, &a, &b, &x, &t);
    if (x == t) return puts("1"), void();
    if (a == 0) return puts(b == t ? "2" : "-1"), void();
    if (a == 1) {
        if ( (t - x + p) % gcd(b, p) ) puts("-1");
        else {
            int ans = ( (t - x + p) * qmi(b, p - 2, p) % p + 1) % p;
            printf("%d\n", (ans == 0) ? p : ans );
        }
        return;
    }
    if ( ( (a * x - x + b) % p + p ) % p == 0 ) return puts("-1"), void();
    int qwq = (t * a - t + b % p + p) % p;
    qwq = qwq * qmi( (a * x - x + b) % p, p - 2, p) % p;
    int ans = BSGS(a, qwq, p);
    printf("%lld\n", (ans == -1) ? -1 : (ans + 1) );
}

signed main() {
    scanf("%d", &T);
    while (T--) solve();
    return 0;
}