Description

Fairland 国有非常严格的法律来规范公司如何组织和支付员工工资：

1. 每家公司必须有且仅有一名 CEO，且 CEO 没有上级。
2. 除 CEO 外，每位员工必须有且仅有一名上级。（这意味着公司的组织结构图是一棵树，没有环。）
3. 只要员工在公司工作，其上级不得更换。这意味着如果一名上级离开，则所有直接下属也必须离开。
4. CEO 绝不能离开公司。
5. 每位员工都有一份工资——每年一定数额的 Fairland 元。员工的工资不得更改。
6. 不同员工的工资可以不同，且员工的工资与其在组织结构中的位置不一定相关。

Fairland 政府刚刚通过了一项新法律：

7. 公司内最高工资与最低工资的差额不得超过 $\mathbf{D}$ Fairland 元。

Marie 是 Fairland General Stuff Corporation 的 CEO，她必须确保公司遵守新法律。这可能需要裁员。她有公司员工名单、各自的上级以及工资信息。请问她最多能保留多少名员工（包括她自己），使得公司仍然符合所有法律规定？

Input Format

输入的第一行为测试用例数 $\mathbf{T}$。接下来有 $\mathbf{T}$ 组测试数据。每组测试数据的第一行为两个用空格分隔的整数 $\mathbf{N}$（员工总数）和 $\mathbf{D}$（允许的最大工资差）。接下来一行包含四个用空格分隔的整数 $\left(\mathbf{S}_{0}, \mathbf{A}_{\mathrm{S}}, \mathbf{C}_{\mathrm{S}}, \mathbf{R}_{\mathrm{S}}\right)$，再下一行包含四个用空格分隔的整数 $\left(\mathbf{M}_{0}, \mathbf{A}_{\mathrm{m}}, \mathbf{C}_{\mathrm{m}}, \mathbf{R}_{\mathrm{m}}\right)$。这八个整数定义了如下序列：

• $\mathbf{S}_{\mathrm{i}+1} = \left(\mathbf{S}_{\mathrm{i}} \times \mathbf{A}_{\mathrm{S}} + \mathbf{C}_{\mathrm{S}}\right) \bmod \mathbf{R}_{\mathrm{S}}$
• $\mathbf{M}_{\mathrm{i}+1} = \left(\mathbf{M}_{\mathrm{i}} \times \mathbf{A}_{\mathrm{m}} + \mathbf{C}_{\mathrm{m}}\right) \bmod \mathbf{R}_{\mathrm{m}}$

Marie 的员工编号为 0，其余员工编号为 $1$ 到 $N-1$。第 $i$ 位员工的工资为 $\mathbf{S}_i$。对于 Marie 以外的每位员工 $i$，其上级编号为 $\mathbf{M}_i \bmod i$。（注意 $\mathbf{M}_0$ 不影响 Marie 的上级——她没有上级！）

Output Format

对于每组测试数据，输出一行，格式为 "Case #x: y"，其中 $x$ 为测试编号（从 1 开始），$y$ 为 Marie 能够保留的最大员工数（包括她自己），使得所有法律 1-7 均被遵守。

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

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

Hint

样例解释

第 1 组数据中，公司只有 CEO 一人，没有其他员工，不违反任何法律，无需做出改变。

第 2 组数据的组织结构如下：

最优策略是保留员工 $0,1,5$（工资分别为 $10,13,8$）。例如，无法保留员工 $2$，因为她的工资与员工 0 的工资 $10$ 相差超过 $5$；由于员工 0 不能被裁员，员工 2 必须被裁掉（以及所有直属于她的员工）。

如果你想检查 1 到 5 号员工的序列如下：

• $\mathbf{S}$：$13,16,2,5,8$
• $\mathbf{M}$：$17,3,13,14,16$
• 上级编号：$17 \bmod 1=0, 3 \bmod 2=1, 13 \bmod 3=1, 14 \bmod 4=2, 16 \bmod 5=1$

数据范围

• $1 \leq T \leq 100$。
• $0 \leq S_0 < R_S$。
• $0 \leq M_0 < R_m$。
• $0 \leq A_S, A_m \leq 1000$。
• $0 \leq C_S, C_m \leq 10^9$。

小数据范围

• 时间限制：5 秒。
• $1 \leq N \leq 1000$。
• $1 \leq D \leq 1000$。
• $1 \leq R_S, R_m \leq 1000$。

大数据范围

• 时间限制：20 秒。
• $1 \leq N \leq 10^6$。
• $1 \leq D \leq 10^6$。
• $1 \leq R_S, R_m \leq 10^6$。

由 ChatGPT 4.1 翻译