鹿 Herbert 正在进行一次徒步旅行：从零度出发，沿着他最喜欢的环形小径顺时针走一圈。Herbert 可以完美控制自己的速度，在任何时候速度都可以是任意非负值（不一定是整数）——他可以随时瞬间改变速度。当 Herbert 再次到达起点时，旅行结束。

这条小径也有人类徒步者使用，他们也沿着小径顺时针行走。每位徒步者都有一个起点，并以各自恒定的速度移动。人类会不停地绕着小径行走。

Herbert 是一只胆小的鹿，害怕人类。他不喜欢与徒步者相遇。每当 Herbert 和某位徒步者在同一时间处于同一地点时，就会发生一次相遇。你应该将 Herbert 和徒步者视为圆周上的点。

Herbert 可能与同一位徒步者发生多次独立的相遇。

如果在同一瞬间遇到多位徒步者，他们每一位都计为一次独立的相遇。

在 Herbert 完成旅行的瞬间发生的任何相遇也计为一次相遇。

如果 Herbert 与某位徒步者相遇，然后改变速度使其与该徒步者的速度完全一致并跟随其后，他就会有无数次相遇！当然，他绝不能这样做。

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

Herbert 知道每位徒步者的起始位置和速度。他可能与徒步者发生的最少相遇次数是多少？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例的第一行包含一个整数 $N$，随后有 $N$ 行，每一行代表一组从路径上同一位置出发的徒步者。这 $N$ 行中的第 $i$ 行包含三个空格分隔的整数：起始位置 $D_i$（表示从鹿的起点沿路径绕行 $D_i/360$ 的距离）、该组中徒步者的数量 $H_i$，以及该组中最快徒步者绕圆圈完成一圈所需的时间 $M_i$（以分钟为单位）。该组中的其他徒步者分别在 $M_i+1, M_i+2, \dots, M_i+H_i-1$ 分钟内完成一圈。例如，行

180 3 4

表示三位徒步者从鹿的起点半圈处出发，他们分别需要 4、5 和 6 分钟绕完一圈。

Herbert 总是从位置 0（绕圆圈的 0/360 处）出发，且没有徒步者组从该位置出发。多组徒步者可能从同一地点出发，但不会有两位徒步者既从同一地点出发又具有相同的速度。

输出格式

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是鹿可能发生的最少相遇次数。

数据范围

内存限制：1 GB。

$1 \le T \le 100$。 $1 \le D_i \le 359$。 $1 \le N \le 1000$。 $1 \le H_i$。 $1 \le M_i \le 10^9$。（注意，这仅限制了每组中最快徒步者完成一圈所需的时间。组内较慢的徒步者所需时间更长。）

子任务 1

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

子任务 2

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

大数据集

时间限制：20 秒。 每个测试用例中的徒步者总数不超过 500,000。

样例

样例输入 1

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

样例输出 1

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

说明

在 Case #1 中，徒步者恰好都以相同的速度移动，Herbert 避免与他们中任何一人相遇的一种方法是保持与他们完全相同的速度移动。

在 Case #2 中，第二位徒步者比第一位移动得快得多，如果 Herbert 为了避免超过第一位徒步者而走得足够慢，他将与快速的第二位徒步者发生多次相遇。Herbert 的一种最优策略是保持与第二位徒步者完全相同的速度，与第一位徒步者相遇一次，而完全不与第二位徒步者相遇。

在 Case #3 中，两位徒步者从同一地点出发，但其中一位的速度是另一位的两倍。一种最优策略是 Herbert 立即追上较慢的徒步者而不超过他，紧随其后直到他经过鹿的起点，然后快速完成旅行，赶在较快的徒步者追上 Herbert 之前结束。