#213337. [GCJ 2015 #1B] Hiking Deer

Herbert Hooves the deer is going for a hike: one clockwise loop around his favorite circular trail, starting at degree zero. Herbert has perfect control over his speed, which can be any nonnegative value (not necessarily an integer) at any time -- he can change his speed instantaneously whenever he wants. When Herbert reaches his starting point again, the hike is over.

The trail is also used by human hikers, who also walk clockwise around the trail. Each hiker has a starting point and moves at her own constant speed. Humans continue to walk around and around the trail forever.

Herbert is a skittish deer who is afraid of people. He does not like to have encounters with hikers. An encounter occurs whenever Herbert and a hiker are in exactly the same place at the same time. You should consider Herbert and the hikers to be points on the circumference of a circle.

Herbert can have multiple separate encounters with the same hiker.

If more than one hiker is encountered at the same instant, all of them count as separate encounters.

Any encounter at the exact instant that Herbert finishes his hike still counts as an encounter.

If Herbert were to have an encounter with a hiker and then change his speed to exactly match that hiker's speed and follow along, he would have infinitely many encounters! Of course, he must never do this.

Encounters do not change the hikers' behavior, and nothing happens when hikers encounter each other.

Herbert knows the starting position and speed of each hiker. What is the minimum number of encounters with hikers that he can possibly have?

The first line of the input gives the number of test cases, . test cases follow. Each begins with one line with an integer , and is followed by lines, each of which represents a group of hikers starting at the same position on the trail. The th of these lines has three space-separated integers: a starting position (representing -ths of the way around the trail from the deer's starting point), the number of hikers in the group, and , the amount of time (in minutes) it takes for the fastest hiker in that group to make each complete revolution around the circle. The other hikers in that group each complete a revolution in , , ..., minutes. For example, the line

180 3 4

would mean that three hikers begin halfway around the trail from the deer's starting point, and that they take 4, 5, and 6 minutes, respectively, to complete each full revolution around the trail.

Herbert always starts at position 0 (-ths of the way around the circle), and no group of hikers does. Multiple groups of hikers may begin in the same place, but no two hikers will both begin in the same place and have the same speed.

For each test case, output one line containing "Case #: ", where is the test case number (starting from 1) and is the minimum number of encounters with hikers that the deer can have.

样例输入 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

Sample Explanation

In Case #1, the hikers all happen to be moving at the same speed, and one way for Herbert to avoid encountering any of them is to move exactly as fast as they do.

In Case #2, the second hiker is moving much faster than the first, and if Herbert goes slowly enough to avoid overtaking the first hiker, he will have multiple encounters with the speedy second hiker. One optimal strategy for Herbert is to go exactly as fast as the second hiker, encountering the first hiker once and never encountering the second hiker at all.

In Case #3, the two hikers start in the same place, but one is twice as fast as the other. One optimal strategy is for Herbert to immediately catch up to the slower hiker without overtaking him, follow just behind him until he passes the deer's starting position, and then finish quickly before the faster hiker can catch Herbert.

Limits

• .
• .
• .
• .
• . (Note that this only puts a cap on the time required for the fastest hiker in each group to complete a revolution. Slower hikers in the group will take longer.)

Small dataset 1

• Time limit: 240 5 seconds.
• The total number of hikers in each test case will not exceed .

Small dataset 2

• Time limit: 240 5 seconds.
• The total number of hikers in each test case will not exceed .

Large dataset

• Time limit: 480 30 seconds.
• The total number of hikers in each test case will not exceed .