Hiking Deer

The deer Herbert Hooves 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 his speed can be any nonnegative real value, not necessarily an integer, and he changes it instantly whenever he wants. The hike ends the moment he reaches his starting point again.

Human hikers use the same trail, and they also walk clockwise. Each hiker has her own starting point and her own constant speed, and every hiker keeps walking around 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 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, and each one is counted.
• If several hikers are met at the same instant, each of them counts as a separate encounter.
• An encounter at the exact instant Herbert finishes his hike 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 the hikers' behavior, 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 has the number of test cases $T$. Each test case begins with a line holding one integer $N$, followed by $N$ lines, each describing a group of hikers who start at the same position on the trail. Each of these lines has three space separated integers $D_i$, $H_i$, $M_i$: the starting position $D_i$ (the group starts $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 the time $M_i$ in minutes that the fastest hiker of the group needs for one complete revolution. The other hikers of that group need $M_i+1$, $M_i+2$, ..., $M_i+H_i-1$ minutes for one 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 take 4, 5, and 6 minutes respectively for one full revolution.

Herbert always starts at position 0, and no group of hikers starts there. Several groups may begin at the same place, but no two hikers both begin at 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 caps only the time the fastest hiker of a group needs. Slower hikers of the same group take longer.)
• The total number of hikers in one test case is at most 10.

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 the deer can have.

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

In test 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 speedy second hiker several times. One optimal plan is to go exactly as fast as the second hiker: he meets the first hiker once and never meets the second one.

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