Hiking Deer (Small1)

Herbert Hooves the deer walks exactly one clockwise loop around his favorite circular trail, starting at degree 0. The hike ends the moment he returns to his starting point. Herbert controls his speed perfectly: at any moment it can be any nonnegative real value (it does not have to be an integer), and he changes it instantly whenever he wants.

Human hikers use the same trail and also walk clockwise. Each hiker has her own starting point and her own constant speed, and she keeps circling the trail forever.

Herbert is a skittish deer who is afraid of people. An encounter happens whenever Herbert and a hiker are at exactly the same place at exactly the same time. Treat Herbert and every hiker as points on the circumference of a circle.

• Herbert can have several separate encounters with the same hiker.
• If he meets more than one hiker at the same instant, each of them counts as a separate encounter.
• An encounter at the exact instant the hike ends still counts.
• If Herbert met a hiker and then matched that hiker's speed exactly and followed along, he would have infinitely many encounters. He never does this.
• Encounters do not change how the hikers walk, and nothing happens when hikers meet each other.

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

The first line of the input gives the number of test cases $T$. Each test case begins with one line with an integer $N$, followed by $N$ lines, each of which 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 $D_i$, $H_i$, $M_i$: the group starts $D_i/360$ of the way around the trail clockwise from the deer's starting point, the group holds $H_i$ hikers, and the fastest hiker of the group needs $M_i$ minutes for each complete lap. The other hikers of that group need $M_i+1$, $M_i+2$, $\dots$, $M_i+H_i-1$ minutes per lap. For example, the line 180 3 4 means that three hikers begin halfway around the trail from the deer's starting point and take 4, 5 and 6 minutes respectively for each lap.

Herbert always starts at position 0, and no group of hikers does. Several groups may begin at the same place, but no two hikers share both a starting place and a lap time.

Limits

• $1 \le T \le 100$
• $1 \le N \le 100$
• $1 \le D_i \le 359$
• $1 \le H_i$
• $1 \le M_i \le 10^9$ (this bound applies only to the fastest hiker of each group; the slower hikers of the group take longer)
• The total number of hikers in one test case is at most 500.
• The total number of hikers over all test cases is at most 2000.

For each test case, output one line containing Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum number of encounters the deer can have.

In case 1 of the sample the four hikers all move at the same speed, so Herbert can move exactly as fast as they do and meet nobody.

In case 2 the second hiker is much faster than the first. If Herbert goes slowly enough not to overtake the first hiker, he meets the fast second hiker several times. One optimal plan is to move exactly as fast as the second hiker: he meets the first hiker once and never meets the second one.

In case 3 the two hikers start at the same place, but one is twice as fast as the other. One optimal plan is to catch up to the slower hiker without passing him, stay right behind him until he passes the deer's starting point, then finish the lap quickly before the faster hiker catches up.