Professor Alex is an expert in the study of ancient buildings.
When he was surveying an ancient temple, he found ruins containing several fallen stone pillars. There are $n$ stone pillars in the ruins, numbered $1, 2, \\\\cdots, n$. For each $i in {1, 2, \\\\cdots, n -1}$, the $(i + 1)^(upright t h)$ stone pillar is next to the $i^(upright t h)$ stone pillar from west to east. As time went on, some stone pillars were badly destroyed.
Each stone pillar can be regarded as a series of continuous cubic stones, and we label the cubic stones $1, 2, 3, \\\\cdots, 10^9$ from south to north. Every two east-west adjacent cubic stones have the same label. The $i^(upright t h)$ stone pillar remains cubic stones $l_i, l_i + 1, \\\\cdots, r_i$.
Here is an example: $n = 4, {l_i} = {4, 2, 3, 3}, {r_i} = {5, 5, 6, 4}$,
Whenever a year goes by, the outer cubic stone will be destroyed by acid rain. In the above example, those blue squares will disappear one year later. Alex wants to know when the all of cubic stones of the $i^(upright t h)$ stone pillar will disappear for each $i = 1, 2, \\\\cdots, n$. Assume that the $i^(upright t h)$ stone pillar will disappear $f_i$ years later. You need to output the answer: $$ \mathrm{answer} = \sum_{i=1}^{n} f_i \cdot 3^{i-1} \bmod 998244353 $$ Since the number of stone pillars can be very large, we generate the test data in a special way. We will provide five parameters $L, X, Y, A, B$, and please refer to the code (written in C++) below:
The first line of the input gives the number of test cases, $T " "(1 <= T <= 10^4)$. $T$ test cases follow.
For each test case, the first line contains two integers $n " "(1 <= n <= 5 times 10^6)$ and $L " "(1 <= L <= 5 times 10^8)$, where $n$ is the number of stone pillars and $L$ is the number of possible value of $l_i$ and $r_i$.
The second line contains two integers $X$ and $Y " "(1 <= X, Y <= 5 times 10^8)$, where $X$ is the minimum possible value of $l_i$ and $Y$ is the minimum possible value of $r_i$.
The last line contains two integers $A$ and $B " "(0 <= A, B < 2^(64))$, representing the initial seed.
The sum of $n$ in all test cases doesn't exceed $1. 2 times 10^7$.
For each test case, output one line containing "_Case #x: y_", where $texttt(x)$ is the test case number (starting from $1$), and $texttt(y)$ is the answer modulo $998244353$.
## Input
The first line of the input gives the number of test cases, $T " "(1 <= T <= 10^4)$. $T$ test cases follow.For each test case, the first line contains two integers $n " "(1 <= n <= 5 times 10^6)$ and $L " "(1 <= L <= 5 times 10^8)$, where $n$ is the number of stone pillars and $L$ is the number of possible value of $l_i$ and $r_i$.The second line contains two integers $X$ and $Y " "(1 <= X, Y <= 5 times 10^8)$, where $X$ is the minimum possible value of $l_i$ and $Y$ is the minimum possible value of $r_i$.The last line contains two integers $A$ and $B " "(0 <= A, B < 2^(64))$, representing the initial seed.The sum of $n$ in all test cases doesn't exceed $1. 2 times 10^7$.
## Output
For each test case, output one line containing "_Case #x: y_", where $texttt(x)$ is the test case number (starting from $1$), and $texttt(y)$ is the answer modulo $998244353$.
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of stone pillars.
Let $ l_i, r_i \in \mathbb{Z}^+ $ denote the southmost and northmost labels of cubic stones remaining in pillar $ i $, for $ i \in \{1, \dots, n\} $.
The height of pillar $ i $ is $ h_i = r_i - l_i + 1 $.
Let $ f_i \in \mathbb{Z}^+ $ be the number of years until pillar $ i $ is completely destroyed, defined as:
$$
f_i = \min(l_i - 1, \, r_i - l_i + 1, \, 10^9 - r_i) + 1
$$
*(Each year, the outermost layer of cubic stones is eroded; the pillar vanishes when the last stone is removed.)*
Let $ X, Y, A, B $ be parameters used to generate $ l_i, r_i $ via a pseudo-random sequence:
- $ l_1 = X $, $ r_1 = Y $
- For $ i \geq 2 $:
$$
l_i = (A \cdot l_{i-1} + B) \bmod L + 1, \quad r_i = (A \cdot r_{i-1} + B) \bmod L + 1
$$
**Constraints**
1. $ 1 \leq T \leq 10^4 $
2. $ 1 \leq n \leq 5 \times 10^6 $, $ 1 \leq L \leq 5 \times 10^8 $
3. $ 1 \leq X, Y \leq 5 \times 10^8 $, $ 0 \leq A, B < 2^{64} $
4. Total $ \sum n \leq 1.2 \times 10^7 $
**Objective**
Compute:
$$
\text{answer} = \left( \sum_{i=1}^{n} f_i \cdot 3^{i-1} \right) \bmod 998244353
$$