给定一个由递推关系定义的生成器：

$$X_{n+1} = ((aX_n + c) \pmod 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 \pmod {(X_j + 1)})$$

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$，表示测试用例的数量。接下来描述所有测试用例。对于每个测试用例： 仅一行，包含八个整数 $m, a, c, X_0, l_1, r_1, l_2, r_2$。

• $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$。

输出格式

对于每个测试用例，输出一行 “Case #x: y”，其中 $x$ 是从 1 开始的测试用例编号，$y$ 是该测试用例的答案。

样例

输入 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

说明

在第一个样例中，$\{X_n\}_{n=0}^{\infty} = \{1, 5, 2, 6, 3, 0, \dots\}$。 在第二个样例中，$\{X_n\}_{n=0}^{\infty} = \{1, 9, 3, 5, \dots\}$。