Hiking Deer (Large)

Herbert the deer is going for a hike: one clockwise loop around his favorite circular trail, starting at degree 0. Herbert has perfect control over his speed. At any moment it can be any nonnegative value, not necessarily an integer, and he can change it instantly whenever he wants. The hike is over when Herbert reaches his starting point again.

Human hikers use the trail as well, and they also walk clockwise. Each hiker has her own starting point and her own constant speed, and the hikers keep walking around the trail forever.

Herbert is a skittish deer who is afraid of people, so he does not like to have encounters with hikers. An encounter happens whenever Herbert and a hiker are in exactly the same place at the same time. Treat Herbert and the hikers as points on the circumference of a circle.

Herbert can have several separate encounters with the same hiker. If he encounters more than one hiker at the same instant, all of them count as separate encounters. An encounter at the exact instant that Herbert finishes his hike still counts. If Herbert had an encounter with a hiker and then changed his speed to exactly match that hiker's speed and followed along, he would have infinitely many encounters, so he never does this. An encounter does not change how a hiker walks, and nothing happens when two hikers meet each other.

Herbert knows the starting position and the speed of every hiker. Find the minimum number of encounters with hikers that he can possibly have.

The first line has the number of test cases $T$. Each test case begins with a line containing one integer $N$, followed by $N$ lines. Each of those lines describes a group of hikers who start at the same position on the trail. The $i$-th of these lines has three space separated integers: a starting position $D_i$, which means $D_i/360$ of the way around the trail from the deer's starting point, the number $H_i$ of hikers in the group, and $M_i$, the time in minutes that the fastest hiker of the group needs for one full revolution. The other hikers of that group need $M_i+1, M_i+2, \dots, M_i+H_i-1$ minutes per revolution.

For example, the line 180 3 4 means that three hikers begin halfway around the trail from the deer's starting point, and that they need 4, 5, and 6 minutes respectively for one full revolution.

Herbert always starts at position 0, and no group of hikers does. Several groups of hikers may begin in the same place, but no two hikers both begin in the same place and have the same speed.

Limits:

• $1 \le T \le 100$
• $1 \le N \le 1000$
• $1 \le D_i \le 359$
• $1 \le H_i$
• $1 \le M_i \le 10^9$. This bounds only the fastest hiker of each group, so the slower hikers of a group take longer.
• The total number of hikers in one test case is at most $500000$.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum number of encounters with hikers that the deer can have.

In the first case of the sample, the four hikers all move at the same speed, and one way for Herbert to avoid every encounter is to move exactly as fast as they do.

In the second case, the second hiker is much faster than the first one. If Herbert goes slowly enough never to overtake the first hiker, he has several encounters with the speedy second hiker. One optimal strategy is to go exactly as fast as the second hiker: Herbert then meets the first hiker once and never meets the second one.

In the third case, the two hikers start in the same place, but one is twice as fast as the other. One optimal strategy is to catch up to the slower hiker at once without overtaking him, stay just behind him until he passes the deer's starting position, and then finish quickly before the faster hiker can catch the deer.