선형 합동 생성기

점화식

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

으로 정의되는 생성기가 주어진다. 여기서 $X = \{X_n\}_{n=0}^{\infty}$는 생성되는 의사 난수 수열이고, $m$, $a$, $c$, $X_0$는 생성기를 결정하는 정수 상수이다.

또한 두 정수 구간 $[l_1, r_1]$과 $[l_2, r_2]$가 주어진다. 다음 값을 계산하라.

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

입력은 여러 개의 테스트 케이스로 이루어진다. 첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 다음에 모든 테스트 케이스가 주어진다. 각 테스트 케이스는 다음과 같다.

한 줄에 여덟 개의 정수 $m$, $a$, $c$, $X_0$, $l_1$, $r_1$, $l_2$, $r_2$가 주어진다.

각 테스트 케이스마다 한 줄에 “Case #x: y”를 출력한다. 여기서 x는 1부터 시작하는 테스트 케이스 번호이고, y는 이 테스트 케이스의 답이다.

• $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$
• 모든 테스트 케이스에서 $m$의 합은 $2 \times 10^6$을 넘지 않는다.

첫 번째 예제에서 $X = \{X_n\}_{n=0}^{\infty} = \{1, 5, 2, 6, 3, 0, \dots\}$이다.

두 번째 예제에서 $X = \{X_n\}_{n=0}^{\infty} = \{1, 9, 3, 5, \dots\}$이다.