Cruise Control (Small)

Cruise control is a system that lets a car hold a constant speed while the driver only steers. The driver can of course switch cruise control off to avoid a collision.

This problem uses a one way road with two lanes and $N$ cars driving on it with cruise control. Every car is 5 meters long and drives at its own constant speed. A car may change lanes at any moment as long as the change causes no collision. Two cars touching is not a collision. A lane change is instantaneous and only moves the car to the other lane. Two cars driving side by side cannot swap places by changing lanes at the same moment. Decide whether somebody eventually has to switch cruise control off to avoid a collision, or whether every car can keep its speed forever while changing lanes whenever it needs to.

The first line has the number of test cases $T$. The first line of each test case has the number of cars $N$. The next $N$ lines describe one car each. A line has a character $C_i$ that tells which lane the car starts in, the speed $S_i$ of the car in meters per second, and the starting position $P_i$ of the car in meters. $P_i$ is the distance from the rear end of the car to a fixed line drawn across the road. Every car drives away from that line and no car is behind it.

Limits

• $1 \le T \le 30$
• $1 \le N \le 6$
• $1 \le S_i \le 1000$
• $0 \le P_i \le 10000$
• $C_i$ is either L for the left lane or R for the right lane.
• The cars do not collide at the start, so if cars $i$ and $j$ start in the same lane ($C_i = C_j$) then $|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. If every car can keep its given speed forever, $y$ is the word Possible. Otherwise $y$ is the largest number of seconds the cars can drive before somebody has to change speed.

That time is always rational, so print it exactly as an irreducible fraction. If the answer is an integer $a$, print only $a$. Otherwise print $a/b$ with $b \ge 2$ and $\gcd(a, b) = 1$. For example, print 7/5 for an answer of 1.4 seconds and 12 for an answer of 12 seconds. A decimal answer is judged wrong.

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

The first test case of the second example has an answer that is not an integer. Two pairs of cars overlap at the start and cannot leave their lanes, and the road is blocked after 13/6 seconds.