크루즈 컨트롤 (스몰)

크루즈 컨트롤은 운전자가 핸들만 조작해도 자동차가 일정한 속도로 달리게 해 주는 장치다. 물론 운전자는 충돌을 피하려고 크루즈 컨트롤을 끌 수 있다.

이 문제에서는 차선이 두 개인 일방통행 도로와 그 위를 크루즈 컨트롤로 달리는 자동차 $N$대를 생각한다. 자동차는 모두 길이가 5미터이고 각자 일정한 속도로 달린다. 자동차는 충돌이 일어나지 않는다면 언제든지 차선을 바꿀 수 있다. 두 자동차가 닿기만 하는 것은 충돌이 아니다. 차선 변경은 순간적으로 일어나고, 자동차가 반대편 차선으로 옮겨 가기만 한다고 가정한다. 나란히 달리는 두 자동차가 같은 순간에 차선을 바꿔 자리를 맞바꾸는 것은 불가능하다. 언젠가 누군가는 충돌을 피하려고 크루즈 컨트롤을 꺼야 하는지, 아니면 모든 자동차가 필요할 때마다 차선을 바꾸면서 속도를 유지한 채 영원히 달릴 수 있는지 판단하라.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스의 첫째 줄에는 자동차의 수 $N$이 주어진다. 이어지는 $N$개의 줄에는 자동차 한 대의 정보가 주어진다. 각 줄에는 자동차가 처음에 있는 차선을 나타내는 문자 $C_i$, 자동차의 속도 $S_i$(초당 미터), 자동차의 처음 위치 $P_i$(미터)가 주어진다. $P_i$는 도로를 가로지르는 고정된 기준선에서 자동차 뒷면까지의 거리다. 모든 자동차는 기준선에서 멀어지는 방향으로 달리고, 기준선보다 뒤에 있는 자동차는 없다.

제한

• $1 \le T \le 30$
• $1 \le N \le 6$
• $1 \le S_i \le 1000$
• $0 \le P_i \le 10000$
• $C_i$는 왼쪽 차선을 뜻하는 L이거나 오른쪽 차선을 뜻하는 R이다.
• 처음에 자동차끼리 충돌하지 않는다. 즉 자동차 $i$와 자동차 $j$의 처음 차선이 같으면($C_i = C_j$) $|P_i - P_j| \ge 5$이다.

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. $x$는 1부터 시작하는 테스트 케이스 번호다. 모든 자동차가 주어진 속도를 유지한 채 영원히 달릴 수 있으면 $y$는 Possible이고, 그렇지 않으면 $y$는 누군가가 속도를 바꿔야 하기 전까지 달릴 수 있는 최대 시간(초)이다.

이 시간은 항상 유리수이므로 기약분수로 정확히 출력한다. 답이 정수 $a$이면 $a$만 출력하고, 정수가 아니면 $b \ge 2$이고 $\gcd(a, b) = 1$인 $a/b$ 꼴로 출력한다. 예를 들어 답이 1.4초이면 7/5를, 12초이면 12를 출력한다. 소수로 출력한 답은 오답으로 처리한다.

첫 번째 예제의 첫 테스트 케이스에서는 빠른 자동차가 오른쪽 차선으로 옮겨 느린 자동차를 어렵지 않게 앞지른다. 두 번째 테스트 케이스에서는 초당 100미터로 나란히 달리는 두 자동차가 10초 뒤에 초당 50미터로 달리는 자동차를 따라잡는데, 두 차선이 모두 막혀 있으므로 누군가는 속도를 바꿔야 한다.

두 번째 예제의 첫 테스트 케이스는 답이 정수가 아닌 경우다. 처음에 위치가 겹친 두 쌍이 서로 차선을 바꾸지 못한 채 13/6초 뒤에 막힌다.