시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 6 4 4 66.667%

## 문제

You are given a generator defined by the recurrence relation

$X_{n+1} = ((a X_n + c) \mod {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_{i=l_2}^{r_2}(X_i \mod {(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$$.

## 예제 입력 1

2
7 1 4 1 2 3 4 5
10 3 6 1 2 3 1 2


## 예제 출력 1

Case #1: 4
Case #2: 12


## 힌트

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\}$$.