로봇의 신뢰

Blue와 Orange는 사이좋은 로봇이다. 사악한 컴퓨터 천재가 이들을 시험하고 어쩌면 케이크를 주기 위해 서로 다른 복도에 가두었다.

각 복도에는 양의 정수 {1, 2, ..., 100}가 표시된 100개의 버튼이 있다. 버튼 k는 항상 복도 시작점에서 k미터 떨어져 있으며, 두 로봇은 모두 버튼 1에서 시작한다. 일 초 동안 로봇은 어느 한 방향으로 일 미터를 이동하거나, 현재 위치의 버튼을 한 번 누르거나, 버튼을 누르지 않고 현재 위치에 머무를 수 있다. 시험을 완료하려면 로봇들은 정해진 버튼 수열을 정해진 순서대로 눌러야 한다. 두 로봇은 전체 수열을 미리 알고 있다. 이들은 얼마나 빨리 시험을 완료할 수 있는가?

예를 들어, 다음 버튼 수열을 살펴보자.

O 2, B 1, B 2, O 4

여기서 O 2는 Orange의 복도에 있는 버튼 2를, B 1는 Blue의 복도에 있는 버튼 1를 뜻하며, 나머지도 같은 방식이다. 로봇들은 아래에 제시된 전략을 사용하여 6초 만에 이 버튼 수열을 누를 수 있다.

Time | Orange           | Blue
-----+------------------+-----------------
  1  | Move to button 2 | Stay at button 1
  2  | Push button 2    | Stay at button 1
  3  | Move to button 3 | Push button 1
  4  | Move to button 4 | Move to button 2
  5  | Stay at button 4 | Push button 2
  6  | Push button 4    | Stay at button 2

Blue는 Orange가 O 2 누르기를 완전히 마칠 때까지 기다려야 B 1 누르기를 시작할 수 있다는 점에 유의하라.

제한

1 ≤ $P_{i}$ ≤ 100 모든 i에 대해. 메모리 제한: 1GB.

작은 데이터 세트 (테스트 세트 1 - 공개)

1 ≤ T ≤ 20. 1 ≤ N ≤ 10. 시간 제한: 30초.

큰 데이터 세트 (테스트 세트 2 - 비공개)

1 ≤ T ≤ 100. 1 ≤ N ≤ 100. 시간 제한: 60초.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다.

각 테스트 케이스는 눌러야 하는 버튼의 수를 나타내는 양의 정수 N으로 시작하는 한 줄로 이루어진다. 그 뒤에는 "$R_{i}$ $P_{i}$" 형식의 항 N개가 주어진다. 여기서 $R_{i}$는 로봇의 색상이며 항상 'O' 또는 'B'이고, $P_{i}$는 버튼의 위치이다.

각 테스트 케이스마다 "Case #x: y"를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며 1부터 시작하고, y는 로봇들이 주어진 버튼을 순서대로 누르는 데 필요한 최소 시간(초)이다.