Fairland 的法律对公司组织架构和员工薪酬有着严格的规定：

1. 每家公司必须有且仅有一名 CEO，且该 CEO 没有上级。
2. 除 CEO 外，每名员工必须有且仅有一名上级。（这意味着展示公司所有员工的组织架构图是一棵树，且不存在环。）
3. 只要员工还在公司工作，其上级就不得变更。这意味着如果一名经理离职，那么所有向该经理汇报的员工也必须离职。
4. CEO 不得离职。
5. 每名员工都会获得一份薪水——每年一定数量的 Fairland 元。员工的薪水不得变更。
6. 不同员工的薪水可能不同，且员工的薪水与其在组织架构图中的位置不一定相关。

Fairland 政府刚刚通过了一条额外法律：

7. 公司内最高薪水与最低薪水之间的差额最多为 D Fairland 元。

Marie 是 Fairland General Stuff Corporation 的 CEO，她必须确保公司遵守新法律。这可能需要裁掉一些员工。她拥有公司员工名单、他们的上级以及他们的薪水。请问她最多能保留多少名员工（包括她自己）？

输入格式

输入的第一行包含测试用例的数量 T。接下来是 T 个测试用例。每个用例的第一行包含两个空格分隔的整数 N（员工数量）和 D（允许的最大薪水差）。接下来的一行包含四个空格分隔的整数（S₀, A_s, C_s, R_s），再下一行包含另外四个空格分隔的整数（M₀, A_m, C_m 和 R_m）。这最后八个整数定义了以下序列：

• S_i+1 = (S_i * A_s + C_s) mod R_s
• M_i+1 = (M_i * A_m + C_m) mod R_m

Marie 的员工 ID 为 0，所有其他员工的 ID 从 1 到 N - 1（包含）。员工 i 的薪水为 S_i。对于除 Marie 以外的每名员工 i，其上级为 M_i mod i。（注意，这意味着 M₀ 不影响 Marie 的上级——她没有上级！）

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 x 是测试用例编号（从 1 开始），y 是 Marie 在遵守法律 1-7 的前提下，公司能保留的最大员工人数（包括她自己）。

数据范围

内存限制：1 GB。

1 ≤ T ≤ 100。

0 ≤ S₀ < R_s。

0 ≤ M₀ < R_m。

0 ≤ A_s, A_m ≤ 1000。

0 ≤ C_s, C_m ≤ 10⁹。

小数据集

时间限制：10 秒。

1 ≤ N ≤ 1000。

1 ≤ D ≤ 1000。

1 ≤ R_s, R_m ≤ 1000。

大数据集

时间限制：20 秒。

1 ≤ N ≤ 10⁶。

1 ≤ D ≤ 10⁶。

1 ≤ R_s, R_m ≤ 10⁶。

样例

输入 1

3
1 395
18 246 615815 60
73 228 14618 195
6 5
10 1 3 17
5 2 7 19
10 13
28 931 601463 36
231 539 556432 258

输出 1

Case #1: 1
Case #2: 3
Case #3: 5

说明

在 Case #1 中，公司只有一名 CEO，没有其他员工，这不违反任何法律，因此无需进行任何更改。

以下是 Case #2 的组织架构图：

最优策略是保留员工 0、1 和 5（他们的薪水分别为 10、13 和 8）。例如，无法保留员工 2，因为她的薪水与员工 0 的薪水 10 之间的差值超过了 5；由于员工 0 不能被裁掉，员工 2 必须被裁掉（连同所有向她汇报的员工一起）。

如果你想核对员工 1 到 5 的序列，它们是：

S: 13, 16, 2, 5, 8

M: 17, 3, 13, 14, 16

上级编号：17 % 1 = 0, 3 % 2 = 1, 13 % 3 = 1, 14 % 4 = 2, 16 % 5 = 1