Description

鹿 Herbert Hooves 要去徒步旅行：他将顺时针绕着他最喜欢的环形小径走一圈，从 $0$ 度起点出发。Herbert 可以完美地控制自己的速度，随时可以选择任意非负速度（不一定是整数），并且可以随时瞬间改变速度。当 Herbert 再次回到起点时，徒步旅行就结束了。

这条小径也有其他人类徒步者，他们也会顺时针绕着小径行走。每个人类徒步者有自己的起点，并以自己的恒定速度行走。人类徒步者会一直不停地绕圈行走。

Herbert 是一只胆小的鹿，他害怕人类。他不喜欢与徒步者“相遇”。当 Herbert 和某个人类徒步者在同一时刻、同一位置时，就算作一次“相遇”。你可以将 Herbert 和徒步者都视为圆周上的点。

Herbert 可能会与同一个徒步者多次相遇。

如果在同一时刻遇到多名徒步者，每个人都算作一次单独的相遇。

如果 Herbert 在完成徒步旅行的那一刻与某个徒步者相遇，这也算作一次相遇。

如果 Herbert 与某个徒步者相遇后，选择与该徒步者速度完全相同并一直跟随，那么他会与该徒步者发生无限多次相遇！当然，他绝不能这样做。

相遇不会影响徒步者的行为，徒步者之间相遇也不会发生任何事情。

Herbert 已经知道每个徒步者的起点和速度。请你计算，Herbert 最少会与多少名徒步者相遇？

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为一个整数 $N$，接下来有 $N$ 行，每行描述一组起点相同的徒步者。第 $i$ 行包含三个用空格分隔的整数：起点 $D_i$（表示距离鹿的起点 $D_i/360$ 圆周长度），该组徒步者人数 $H_i$，以及该组中最快徒步者每圈所需时间 $M_i$（单位为分钟）。该组的其他徒步者每圈所需时间分别为 $M_i+1$，$M_i+2$，……，$M_i+H_i-1$ 分钟。例如：

180 3 4

表示有三名徒步者从距离鹿起点一半圆周的位置出发，他们每圈分别需要 $4$、$5$、$6$ 分钟。

Herbert 总是从 $0$ 位置（$0/360$ 圆周长度）出发，且没有徒步者从该点出发。多个徒步者组可以从同一位置出发，但不会有两名徒步者既起点相同又速度相同。

Output Format

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是鹿最少会遇到的徒步者人数。

3
4
1 1 12
359 1 12
2 1 12
358 1 12
2
180 1 100000
180 1 1
1
180 2 1

Case #1: 0
Case #2: 1
Case #3: 0

Hint

样例解释

第 1 组中，所有徒步者速度相同，Herbert 可以选择与他们相同的速度，从而完全避免相遇。

第 2 组中，第二名徒步者速度远快于第一名。如果 Herbert 选择足够慢的速度以避免追上第一名徒步者，他会与第二名徒步者多次相遇。最优策略是选择与第二名徒步者相同的速度，这样只会与第一名徒步者相遇一次，永远不会遇到第二名徒步者。

第 3 组中，两名徒步者起点相同，但其中一人速度是另一人的两倍。最优策略是：Herbert 立即追上较慢的徒步者但不超过他，紧跟其后直到该徒步者经过鹿的起点，然后在更快的徒步者追上之前迅速完成剩余路程。

数据范围

• $1 \leq T \leq 100$。
• $1 \leq D_i \leq 359$。
• $1 \leq N \leq 1000$。
• $1 \leq H_i$。
• $1 \leq M_i \leq 10^9$。（注意，这只是限制每组中最快徒步者每圈所需的最短时间。组内较慢的徒步者每圈所需时间更长。）

小数据集 1

• 时间限制：5 秒。
• 每个测试用例中徒步者总数不超过 $2$。

小数据集 2

• 时间限制：5 秒。
• 每个测试用例中徒步者总数不超过 $10$。

大数据集

• 时间限制：30 秒。
• 每个测试用例中徒步者总数不超过 $500000$。

由 ChatGPT 4.1 翻译