Linear Congruential Generator

You are given a generator defined by the recurrence relation

$X_{n+1} = ((a X_n + c) \bmod {m})$

where $X = \{X_n\}_{n=0}^{\infty}$ is the generated sequence of pseudorandom values, and $m$, $a$, $c$, $X_0$ are integer constants which specify the generator.

Additionally, two integer intervals $[l_1, r_1]$ and $[l_2, r_2]$ are given. Please calculate

$\sum_{i=l_1}^{r_1}\sum_{j=l_2}^{r_2}(X_i \bmod {(X_j + 1)})$

The input contains several test cases. The first line contains an integer $T$ indicating the number of test cases. The following describes all test cases. For each test case:

The only line contains eight integers $m$, $a$, $c$, $X_0$, $l_1$, $r_1$, $l_2$, $r_2$.

For each test case, output a line containing “Case #x: y” (without quotes), where x is the test case number starting from 1, and y is the answer to this test case.

• $1 \le T \le 10^5$
• $1 \le m \le 10^6$
• $0 \le a, c, X_0 < m$
• $0 \le l_1 \le r_1 \le 10^6$
• $0 \le l_2 \le r_2 \le 10^6$
• The sum of $m$ in all test cases does not exceed $2 \times 10^6$.

In the first sample case, $X = \{X_n\}_{n=0}^{\infty} = \{1, 5, 2, 6, 3, 0, \dots\}$.

In the second sample case, $X = \{X_n\}_{n=0}^{\infty} = \{1, 9, 3, 5, \dots\}$.