你正在研究中国长城的历史，长城是由中国人建造的，旨在抵御来自北方的军事入侵。在本题中，长城从东方的无穷远处延伸至西方的无穷远处。由于距离极其漫长，长城并非一次性建成。相反，我们假设建造者采取了一种反应式策略：每当边境的某一部分受到成功攻击时，该段长城的防御高度就会被提升至足以抵御未来同等强度攻击的高度。

中国北方的边境经常受到游牧部落的攻击。在本题中，我们假设每个部落都在某个区间内以强度 $S$ 对边境发起攻击。为了击退攻击，长城在受攻击的整个区间内必须具备至少 $S$ 的高度。如果长城中哪怕有一小段的高度低于所需强度，攻击就会在该点突破长城并获得成功。注意，即使是成功的攻击也不会损坏长城。攻击发生后，长城中所有高度低于 $S$ 的受攻击片段都会被提升至高度 $S$ —— 换句话说，长城以能够阻止该次攻击的最小方式进行加固。注意，如果两次或多次攻击发生在同一天，长城会在所有攻击结束后统一进行加固，且加固方式为能够阻止所有这些攻击的最小方式。

由于游牧部落具有迁徙性，他们并不一定局限于单次攻击。相反，他们倾向于移动（向东或向西），并周期性地攻击长城。为了简化问题，我们假设他们以恒定速度移动，并以固定的时间间隔攻击长城；此外，我们假设给定部落攻击长城的强度在每次攻击后都会发生恒定的变化（可能因损耗而降低，也可能因经验积累而增长）。

假设最初（公元前 250 年）长城并不存在（即处处高度为零），在给定所有攻击长城的游牧部落的完整描述后，请确定有多少次攻击是成功的。

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$，表示攻击长城的部落数量。接下来有 $N$ 行，每行描述一个部落。第 $i$ 行包含八个整数 $d_i, n_i, w_i, e_i, s_i, \text{delta\_d}_i, \text{delta\_p}_i$ 和 $\text{delta\_s}_i$，用空格分隔，描述一个游牧部落：

• $d_i$ —— 该部落第一次攻击的日期（公元前 250 年 1 月 1 日记为第 0 天）
• $n_i$ —— 该部落发起的攻击次数
• $w_i, e_i$ —— 第一次攻击时受攻击长城的西端点和东端点
• $s_i$ —— 第一次攻击的强度
• $\text{delta\_d}_i$ —— 该部落后续攻击之间的时间间隔（天数）
• $\text{delta\_p}_i$ —— 该部落在后续攻击之间向东移动的距离（如果为负，则表示向西移动）
• $\text{delta\_s}_i$ —— 后续攻击之间强度的变化量

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是用例编号（从 1 开始），$y$ 是成功的攻击次数。

数据范围

时间限制：12 秒。

内存限制：1GB。

$1 \le T \le 20$。

$0 \le d_i$。

$1 \le \text{delta\_d}_i \le 676060$。

$d_i + (n_i - 1) \times \text{delta\_d}_i \le 676060$。

$1 \le s_i \le 10^6$。

$-10^5 \le \text{delta\_s}_i \le 10^5$。

$s_i + (n_i - 1) \times \text{delta\_s}_i \ge 1$。

小数据集（测试集 1 - 可见；9 分）

$1 \le N \le 10$。

$1 \le n_i \le 10$。

$-100 \le w_i < e_i \le 100$。

$-10 \le \text{delta\_p}_i \le 10$。

大数据集（测试集 2 - 隐藏；28 分）

$1 \le N \le 1000$。

$1 \le n_i \le 1000$。

$-10^6 \le w_i < e_i \le 10^6$。

$-10^5 \le \text{delta\_p}_i \le 10^5$。

样例

样例输入 1

2
2
0 3 0 2 10 2 3 -2
10 3 2 3 8 7 2 0
3
1 2 0 5 10 2 8 0
0 3 0 1 7 1 2 2
3 3 0 5 1 1 4 0

样例输出 1

Case #1: 5
Case #2: 6

说明

在第一个用例中，第一个部落攻击了三次：第 0 天以强度 10 攻击区间 $[0,2]$，第 2 天以强度 8 攻击区间 $[3,5]$，第 4 天以强度 6 攻击区间 $[6,8]$；这三次攻击均成功。随后第二个部落攻击了三次，每次强度均为 8 —— 第 10 天攻击 $[2,3]$（成功，例如在位置 2.5 处，长城高度仍为 0），第 17 天攻击 $[4,5]$（失败，长城在区间 $[3, 5]$ 内高度已为 8，覆盖了 $[4, 5]$），第 24 天攻击 $[6,7]$（成功，因为该处长城高度为 6）。

在第二个用例中，有三个部落，他们的攻击交织在一起。序列如下： 第 0 天，部落 2 以强度 7 攻击 $[0,1]$ 并成功。 第 1 天，部落 1 以强度 10 攻击 $[0,5]$，部落 2 以强度 9 攻击 $[2,3]$。两次攻击均成功（因为它们是同时发生的，第一个部落攻击后建立的长城来不及阻止第二个部落）。 第 2 天，部落 2 以强度 11 攻击 $[4,5]$ 并成功（该处长城高度为 10）。 第 3 天，部落 1 以强度 10 攻击 $[8,13]$ 并成功。同时，部落 3 以强度 1 攻击 $[0,5]$ 并失败（该处已有高度为 10 和 11 的长城）。 第 4 天，部落 3 以强度 1 攻击 $[4,9]$ 并成功（5 到 8 之间没有长城）。 最后，第 5 天，部落 3 以强度 1 攻击 $[8,13]$ 并失败（因为该处已有高度为 10 的长城）。