闲话：官解给的二分暴力是人想的到的吗？
Alice 将数字去重排序，得到 $v_1 < v_2 < \cdots < v_t$。
我们设 $cnt_i$ 为数字 $v_i$ 的出现次数。
- 若 Alice 选择两个相同的数字 $v_i$，则需要 $cnt_i \ge 2$；
- 若 Alice 选择两个不同的数字，由于不能有数字严格夹在中间，这两个数字只能是排序后相邻的，即 $(v_i, v_{i+1})$。
因此合法数字对只有两类：
- 同值对 $(v_i,v_i)$，当 $cnt_i\ge 2$。
- 相邻不同值对 $(v_i,v_{i+1})$。
那么，对于 Bob 可以随机选择左右手，不妨设各选一半。当 Bob 看到数字 $v_i$ 后，他需要猜另一个数字与 $v_i$ 的大小关系。另一个数字只可能是 $v_{i-1},v_i,v_{i+1}$ 中的一个，因此 Bob 只需给出三个概率：
- 猜 “<” 的概率：$y_i$
- 猜 “=” 的概率：$z_i$
- 猜 “>” 的概率：$x_i$
满足 $x_i+y_i+z_i=1$。边界上，$v_1$ 不可能有更小的另一个数字，所以 $y_1=0$，$v_t$ 不可能有更大的另一个数字，所以 $x_t=0$。
那么就有两种情况：同值对与非同值对。
- 对于同值对 $(v_i,v_i)$，无论 Bob 选哪只手，看到的都是 $v_i$，只有猜 “=” 才能赢，因此胜率为 $z_i$。为保证胜率至少为 $p$，需要 $z_i \ge p \quad [cnt_i\ge 2]$。
- 对于非同值对，Bob 有一半概率看到 $v_i$，此时猜 “>” 可赢，另一半概率看到 $v_{i+1}$，此时猜 “<” 可赢。所以胜率为 $\frac{x_i + y_{i+1}}{2} \ge p$，就是 $x_i + y_{i+1} \ge 2p$。
我们将 $x_i = 1 - y_i - z_i$ 带入，得 $1 - y_i - z_i + y_{i+1} \ge 2p$，移项得 $y_{i+1} - y_i \ge 2p - 1 + z_i$。
对于区间 $[i,j]$ 累加 $y_j - y_i \ge (2p-1)(j-i) + \sum_{k=i}^{j-1} z_k$。
又因为 $y_i \ge 0$，且 $y_j \le 1 - z_j$，所以 $(2p-1)(j-i) + \sum_{k=i}^{j} z_k \le 1$。
我们令 $S_{i,j} = \sum_{k=i}^{j} [cnt_k \ge 2]$。由于 $z_k \ge p$ 对 $c_k\ge 2$ 成立，则有 $(2p-1)(j-i) + p S_{i,j} \le 1$。
我们设区间长度 $L = j-i+1$，带入得 $p \le \frac{L}{2L + S_{i,j} - 2}$。
该不等式对任意区间 $[i,j]$ 均成立，所以 $p \le \min_{1\le i
到这里会有一个值的个数的平方的做法，因为数据过水可以莽过去。
我们接下来想怎么优化到线性。
因为 $S_{i, j} = sum_i - sum_j$，则区间 $[i,j]$ 的 $S = sum_j - sum_{i-1}$。那么原来的答案就可以变为 $\frac{L}{2L + S - 2} = \frac{1}{2 + \dfrac{S-2}{L}}$。
因此最小化原分数等价于最大化 $\frac{S-2}{L} = \frac{sum_j - sum_{i-1} - 2}{j - (i-1)}$。
令左端点 $l = i-1$，则要求$\max_{0 \le l \le j-2} \frac{sum_j - sum_l - 2}{j - l}$。
我们不难发现这是一个下凸壳，可以用队列直接线性维护。
补充证明一：
因为 $x_j+y_j+z_j=1,\quad x_j\ge 0$，则有 $y_j\le 1-z_j$。
同时 $y_i\ge 0$，推出 $y_j-y_i\le y_j\le 1-z_j$。
因此有：$(2p-1)(j-i)+\sum_{k=i}^{j-1}z_k\le y_j-y_i\le 1-z_j$
移项后 $(2p-1)(j-i)+\sum_{k=i}^{j}z_k\le 1$
这里的右边是$1$，是因为 $z_j$ 并在里面，不可能是 $2$ 及其它。
补充证明二：
（一）上界为什么是 $1-z_j$ 而且可达?
因为 Bob 看到数字 $v_j$ 时有 $x_j+y_j+z_j=1,\qquad x_j\ge 0$，则 $y_j\le 1-z_j$
这个上界是可以取等的：令 $x_j=0$，也就是 Bob 看到 $v_j$ 时永远不猜“>”，那么就有 $y_j=1-z_j$。 因此 $y_j\le 1-z_j$ 是 $y_j$ 的精确最大可能值。
（二） 下界为什么是 $0$ 而且可达？
因为概率 $y_i\ge 0$，并且可以取等。特别地，边界上 $v_1$ 不可能有更小的另一个数字，所以 $y_1=0$是强制的。所以下界 $y_i\ge 0$ 也是可达的。所以 $y_j-y_i\le y_j\le 1-z_j$ 中的右边是 $y_j-y_i$ 在可行范围内的最大可能值。
（三） 为什么整体限制是紧的？
我们得到：
$p\le \min_{1\le i
如果最优的 $p$ 使得所有区间都是严格小于，就有 $(2p-1)(j-i)+pS_{i,j}<1$
那么因为不等式关于 $p$ 是连续的，我们可以把 $p$ 再增大一点点，仍然满足所有区间约束。这说明原来的 $p$ 不是最大可行值。所以最优 $p$ 一定会让至少一个区间取等。而单个区间能取等，正是因为我们前面用的上界 $1-z_j$ 和下界 $0$ 都是可达的。
（四）为什么 $p$ 一定连续？
因为每个区间约束的左边是关于 $p$ 的线性连续函数 $(2p-1)(j-i)+pS_{i,j}=p\bigl(2(j-i)+S_{i,j}\bigr)-(j-i)$
其中系数 $2(j-i)+S_{i,j}>0$ 所以它关于 $p$ 是连续且严格递增的。
如果当前 $p$ 使得所有区间都严格成立，则有 $(2p-1)(j-i)+pS_{i,j}<1$。那么左边和 $1$ 之间有一个正差距 $\delta_{i,j}=1-\left[(2p-1)(j-i)+pS_{i,j}\right]>0$。
由于这个式子关于 $p$ 连续，所以只要把 $p$ 增大一点点，左边也只会增大一点点。只要增大的量小于 $\delta_{i,j}$，不等式仍然成立。
现在区间只有有限多个，所以可以取所有 $\delta_{i,j}$ 的最小值 $\delta=\min_{i,j}\delta_{i,j}>0$
连续性保证存在一个 $\varepsilon>0$，使得当 $p$ 增大到 $p+\varepsilon$ 时，每个左边相对于原来的增量都小于 $\delta$，因此仍然严格小于 $1$。
就是 $(2(p+\varepsilon)-1)(j-i)+(p+\varepsilon)S_{i,j}<1$。对所有区间仍成立。
#include<bits/stdc++.h>
#define int long long
// #define int __int128
using namespace std;
const int MOD = 998244353;
int t, n, a[10000005], A, B, C, M, cnt[10000005], sum[10000005], tot, b[10000005], q[10000005], head, tail;
int ksm(int x, int y) {
int res = 1;
while (y) {
if (y & 1) {
res *= x;
res %= MOD;
}
x *= x;
x %= MOD;
y >>= 1;
}
return res;
}
inline void read(int &n){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
n=x*f;
}
inline void print(int n){
if(n<0){
putchar('-');
n*=-1;
}
if(n>9) print(n/10);
putchar(n % 10 + '0');
}
signed main() {
// freopen("game.in", "r", stdin);
// freopen("game.out", "w", stdout);
// ios_base::sync_with_stdio(false);
// cin.tie(0);
// cout.tie(0);
// cin >> t;
read(t);
// inv[0] = 1;
// inv[1] = 1;
// for (int i = 2; i <= 10000000; i ++) {
// inv[i] = inv[MOD % i] * (i - i / MOD) % MOD;
// }
while (t --) {
// cin >> n >> a[0] >> A >> B >> C >> M;
read(n);
read(a[0]);
read(A);
read(B);
read(C);
read(M);
for (int i = 1; i <= n; i ++) {
a[i] = ((A * a[i - 1] % M * a[i - 1] % M + B * a[i - 1] % M + C) % M) + 1;
cnt[a[i]] ++;
}
tot = 0;
for (int i = 1; i <= n; i ++) {
if (cnt[i]) {
b[++tot] = cnt[i];
sum[tot] = sum[tot - 1];
if (cnt[i] >= 2) {
sum[tot] ++;
}
}
}
if (tot == 1) {
// cout << "1\n";
puts("1");
for (int i = 0; i <= n; i ++) {
// sum[i] = 0;
cnt[i] = 0;
}
for (int i = 0; i <= tot; i ++) {
sum[i] = 0;
}
continue;
}
int x = 1, y = 1;
// for (int i = 1; i <= tot; i ++) {
// // int l = i + 1, r = tot, mid = (l + r) >> 1;
// for (int j = i + 1; j <= tot; j ++) {
// if ((j - i + 1) * y < x * (2 * (j - i + 1) + sum[j] - sum[i - 1] - 2)) {
// x = j - i + 1;
// y = 2 * (j - i + 1) + sum[j] - sum[i - 1] - 2;
// }
// }
// }
// if (tot * y < x * (2 * tot + sum[tot] - 2)) {
// x = tot;
// y = 2 * tot + sum[tot] - 2;
// }
// for (int i = 0; i <= tot; i ++) {
// f[i][0] = f[i][1] = 0;
// }
// for (int i = 1; i <= n; i ++) {
// }
// int inv = ksm(n - 1, MOD - 2), minn = n - 1;
// for (int i = 1; i <= n; i ++) {
// minn = min(minn, max(cnt[i], max(sum[i - 1], sum[n] - sum[i])));
// }
// cout << inv * minn % MOD << "\n";
head = 1, tail = 0;
bool flag = false;
int L = 0, S = 0;
for (int i = 1; i <= tot; i ++) {
if (i >= 2) {
while (tail - head >= 1 && (sum[q[tail]] - sum[q[tail - 1]]) * (i - 2 - q[tail]) >= (sum[i - 2] - sum[q[tail]]) * (q[tail] - q[tail - 1])) {
tail --;
}
q[++tail] = i - 2;
}
while (tail - head >= 1 && (sum[i] - sum[q[head]] - 2) * (i - q[head + 1]) <= (sum[i] - sum[q[head + 1]] - 2) * (i - q[head])) {
head ++;
}
if (head <= tail) {
if (!flag) {
L = i - q[head];
S = sum[i] - sum[q[head]];
flag = true;
continue;
}
if ((sum[i] - sum[q[head]] - 2) * L > (S - 2) * (i - q[head])) {
L = i - q[head];
S = sum[i] - sum[q[head]];
}
}
}
x = L;
y = 2 * L + S - 2;
int ans = x * ksm(y, MOD - 2) % MOD;
print(ans);
puts("");
for (int i = 0; i <= n; i ++) {
// sum[i] = 0;
cnt[i] = 0;
}
for (int i = 0; i <= tot; i ++) {
sum[i] = 0;
}
}
return 0;
}
/*
2
4 1 0 1 0 2
4 1 0 1 0 4
*/