Watson and Intervals (Small)

Sherlock and Watson have learned enough C++ in their programming course to move on to algorithmic problems. In today's class the tutor introduced the problem of merging one dimensional intervals. $N$ intervals are given, and the $i$th interval is defined by the inclusive endpoints $[L_i, R_i]$, where $L_i \le R_i$.

The tutor defined the covered area of a set of intervals as the number of integers that appear in at least one of the intervals. Formally, an integer $p$ contributes to the covered area if there is some $j$ with $L_j \le p \le R_j$.

Watson likes to challenge Sherlock. This time he asked Sherlock to remove exactly one interval so that the covered area of the remaining intervals is as small as possible. Find that minimum possible covered area after removing exactly one of the $N$ intervals.

The first line contains the number of test cases $T$.

Each test case consists of one line with eight integers $N$, $L_1$, $R_1$, $A$, $B$, $C_1$, $C_2$, and $M$, separated by spaces. $N$ is the number of intervals and the first interval is $[L_1, R_1]$. The other seven values are the parameters used to generate the remaining intervals.

First set $x_1 = L_1$ and $y_1 = R_1$. Then use the recurrences below to generate $x_i$ and $y_i$ for $i = 2$ to $N$.

• $x_i = (A \times x_{i-1} + B \times y_{i-1} + C_1) \bmod M$
• $y_i = (A \times y_{i-1} + B \times x_{i-1} + C_2) \bmod M$

Define $L_i = \min(x_i, y_i)$ and $R_i = \max(x_i, y_i)$ for all $i = 2$ to $N$.

For each test case, output one line containing Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum possible covered area of the intervals remaining after removing exactly one interval.

• $1 \le T \le 50$
• $1 \le N \le 1000$
• $0 \le L_1 \le R_1 \le 10^9$
• $0 \le A \le 10^9$
• $0 \le B \le 10^9$
• $0 \le C_1 \le 10^9$
• $0 \le C_2 \le 10^9$
• $1 \le M \le 10^9$

In the first case of the example, the generation rule produces the single interval $\{[1, 1]\}$. Removing the only interval leaves a covered area of $0$.

In the second case the generated intervals are $\{[2, 5], [3, 5], [4, 7]\}$. Removing the first, second or third interval leaves a covered area of $5$, $6$ and $4$ respectively.

In the third case the generated intervals are $\{[3, 4], [1, 9], [0, 8], [2, 4]\}$. Removing the first, second, third or fourth interval leaves a covered area of $10$, $9$, $9$ and $10$ respectively.