Bob 被困在一个由 $N$ 行 $M$ 列组成的矩阵表示的洞穴中，行号从 $1$ 到 $N$（从上到下），列号从 $1$ 到 $M$（从左到右）。第 $i$ 行第 $j$ 列的单元格记为 $(i, j)$。

Bob 目前位于单元格 $(S_R, S_C)$，洞穴的出口位于单元格 $(T_R, T_C)$。

洞穴中的每个单元格都包含一个数字，称为魔力值。单元格 $(i, j)$ 的魔力值为 $V_{ij}$。

当 Bob 从一个单元格移动到一个未访问过的单元格时，他获得的能量点数等于这两个单元格魔力值的乘积。这意味着，如果 Bob 从单元格 $(i, j)$ 移动到单元格 $(x, y)$，且单元格 $(x, y)$ 未被访问过，他将获得 $V_{ij} \times V_{xy}$ 点能量。

Bob 可以在共享边的单元格之间移动（不仅仅是角接触）。到达出口单元格时，Bob 可以选择不离开洞穴，如果他愿意，可以继续探索。请帮助他找出他离开洞穴时能获得的最大能量点数。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例包含两行。第一行包含六个整数 $N, M, S_R, S_C, T_R$ 和 $T_C$，含义如上所述。

下一行包含六个整数，格式如下： $X_1 \ X_2 \ A \ B \ C \ P$

这些值用于按以下方式生成 $V_{ij}$： 我们定义： $X_i = (A \times X_{i-1} + B \times X_{i-2} + C) \pmod P$，对于 $i = 3$ 到 $N \times M$。

我们还定义： $V_{ij} = X_{(i-1) \times M + j}$，对于 $i = 1$ 到 $N$，且 $j = 1$ 到 $M$。

$1 \le T \le 10$ $1 \le N, M \le 1000$ $1 \le S_R, T_R \le N$ $1 \le S_C, T_C \le M$ $0 \le X_1, X_2, A, B, C \le P$ $1 \le P \le 100$

输出格式

对于每个测试用例，输出一行包含 “Case #x: y”，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 Bob 能获得的最大能量点数。

样例

输入 1

2
1 4 1 2 1 3
1 2 2 3 1 5
6 1 2 1 4 1
0 1 2 3 0 4

输出 1

Case #1: 17
Case #2: 8

说明

在样例 1 中，矩阵为：

$1 \ 2 \ 3 \ 3$

获得 17 点能量的一种方式是： $(1, 2) \to (1, 1)$，获得 $1 \times 2$ 点能量。 $(1, 1) \to (1, 2)$，获得 $0$ 点能量。 $(1, 2) \to (1, 3)$，获得 $2 \times 3$ 点能量。 $(1, 3) \to (1, 4)$，获得 $3 \times 3$ 点能量。 * $(1, 4) \to (1, 3)$，获得 $0$ 点能量。

在样例 2 中，矩阵为：

$0$ $1$ $2$ $3$ $0$ $1$

获得 8 点能量的一种方式是： $(2, 1) \to (3, 1)$，获得 $1 \times 2$ 点能量。 $(3, 1) \to (4, 1)$，获得 $2 \times 3$ 点能量。