开司（Kaiji）是一个聪明的赌徒，他再次输光了所有的钱，并欠了兵藤和尊（Hyodo Kazutaka）一大笔钱。兵藤和尊非常残忍，他提议玩一个赌上开司四根手指的游戏！

兵藤有一个装有 $n$ 个几乎相同的球的盒子，其中第 $i$ 个球上写有一个整数 $a_i (1 \le i \le n)$，这是球之间唯一的区别。首先，开司会被蒙上眼睛，这意味着他什么也看不见。然后，兵藤会任意选择两个“接近”的球（形式化地说，假设选出的两个球是 $i$ 和 $j$，则不存在 $k$ 使得 $(a_i - a_k)(a_j - a_k) < 0$），将它们从盒子里取出并放入开司的两只手中。之后，开司必须说“左手”或“右手”，兵藤会告诉他所选手中球上的数字。最后，最关键的部分是，开司需要回答所告知的数字与另一只手中球上数字的大小关系（大于、小于或等于）。如果开司的回答正确，他将免除债务，否则他将失去他的手指。

现在，开司需要你的帮助，他想知道无论兵藤采取什么策略，他所能保证的最高获胜概率是多少。

注意：开司在被蒙上眼睛之前会知道所有球上的数字以及完整的规则。

输入格式

第一行包含一个整数 $T (1 \le T \le 1000)$，表示测试用例的数量。

对于每个测试用例： 仅一行包含 6 个整数 $n (2 \le n \le 10^7)$，$a_0, A, B, C (0 \le a_0, A, B, C \le 10^9)$，$M (1 \le M \le n)$，表示球的数量和 $a$ 的生成参数，其中： $$a_i = (A \cdot a_{i-1}^2 + B \cdot a_{i-1} + C) \pmod M + 1 \quad (1 \le i \le n)$$

保证所有测试用例的 $n$ 之和不超过 $10^7$。

输出格式

对于每个测试用例： 输出一行，包含一个整数，表示获胜概率对 998244353 取模的结果。 注意，对于有理数 $\frac{p}{q}$ 和整数 $k (0 \le k < P)$，如果 $kq \equiv p \pmod P$ 成立，我们称 $\frac{p}{q}$ 对 $P$ 取模等于 $k$。在本题中，你可以假设存在唯一的整数等于获胜概率对 998244353 取模的结果。

样例

输入 1

2
4 1 0 1 0 2
4 1 0 1 0 4

输出 1

499122177
665496236

说明

对于第一个测试用例： $n = 4, \{a_1, a_2, a_3, a_4\} = \{2, 1, 2, 1\}$，开司的一种最优策略是： 随机选择左手或右手。然后：

• 如果听到的数字是 1，则以 50% 的概率猜测两个数字相等，以 50% 的概率猜测另一只手中的球上的数字大于所告知的数字。
• 如果听到的数字是 2，则以 50% 的概率猜测两个数字相等，以 50% 的概率猜测另一只手中的球上的数字小于所告知的数字。

在这种策略下，无论兵藤如何选择球，开司都有 50% 的获胜概率。 这里 $499122177 \times 2 \equiv 1 \pmod{998244353}$，且 499122177 是唯一一个对 998244353 取模等于 $\frac{1}{2}$ 的整数，因此答案为 499122177。