Cruise Control (Large)

Cruise control keeps a car at a constant speed while the driver only steers. The driver can of course switch it off to avoid a collision.

This problem uses a one way road with two lanes and $N$ cars driving on it with cruise control on. Every car is 5 meters long and moves at its own constant speed. A car can change lanes at any moment as long as the change does not cause a collision with another car. Two cars that merely touch do not count as a collision. A lane change is instantaneous and does nothing except move the car to the other lane. Even though a lane change is instantaneous, two cars driving side by side cannot exchange places by changing lanes at the same time.

Decide whether all of the cars can keep their given speeds forever without a collision, changing lanes as often as they like, or whether somebody eventually has to switch cruise control off. If somebody has to, report the longest time they can all drive before that moment.

The first line contains the number of test cases $T$.

The first line of each test case contains the number of cars $N$. Each of the next $N$ lines describes one car and contains a character $C_i$ followed by two integers $S_i$ and $P_i$. $C_i$ is the lane the car starts in, L for the left lane and R for the right lane. $S_i$ is the speed of the car in meters per second. $P_i$ is the distance in meters from a fixed line drawn across the road to the rear end of the car. Every car drives away from that line, and no car is behind it.

• $1 \le T \le 30$
• $1 \le N \le 50$
• $1 \le S_i \le 1000$
• $0 \le P_i \le 10000$
• $C_i$ is either L or R.
• The cars do not collide at the start, that is, two cars $i$ and $j$ that start in the same lane satisfy $|P_i - P_j| \ge 5$.

For each test case print one line in the form Case #x: y, where $x$ is the test case number starting from 1. $y$ is Possible if all of the cars can keep their given speeds forever, and otherwise $y$ is the maximum number of seconds they can drive before somebody has to change speed.

Print the time exactly, as an irreducible fraction rather than a decimal. If the answer is $p/q$ with $q \ge 1$ and $\gcd(p, q) = 1$, print p/q when $q$ is at least 2, and print p alone when $q$ is 1. Print 0 when the answer is 0.

In the first case of the example the faster car moves to the right lane and passes the slower one without trouble. In the second case the two cars driving side by side at 100 meters per second catch the car going 50 meters per second after 10 seconds. Both lanes are blocked at that moment, so somebody has to change speed.