Blue và Orange là những chú rô-bốt thân thiện. Một kẻ chủ mưu máy tính độc ác đã nhốt chúng vào các hành lang riêng biệt để kiểm tra chúng, và sau đó có thể sẽ cho chúng ăn bánh.

Mỗi hành lang có 100 nút bấm được đánh số bằng các số nguyên dương \(\{1, 2, \dots, 100\}\). Nút \(k\) luôn cách điểm bắt đầu của hành lang \(k\) mét, và cả hai rô-bốt đều bắt đầu tại nút 1. Trong khoảng thời gian một giây, một rô-bốt có thể đi bộ một mét theo bất kỳ hướng nào, hoặc nó có thể nhấn nút tại vị trí của mình một lần, hoặc nó có thể đứng yên tại vị trí của mình và không nhấn nút. Để hoàn thành bài kiểm tra, các rô-bốt cần nhấn một dãy nút nhất định theo một thứ tự nhất định. Cả hai rô-bốt đều biết toàn bộ dãy nút trước. Chúng có thể hoàn thành bài kiểm tra nhanh nhất là bao lâu?

Ví dụ, hãy xem xét dãy nút sau:
O 2, B 1, B 2, O 4

Ở đây, O 2 nghĩa là nút 2 trong hành lang của Orange, B 1 nghĩa là nút 1 trong hành lang của Blue, và tương tự. Các rô-bốt có thể nhấn dãy nút này trong 6 giây bằng chiến lược dưới đây:

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

Lưu ý rằng Blue phải đợi cho đến khi Orange nhấn xong nút O 2 trước khi nó có thể bắt đầu nhấn nút B 1.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\). Tiếp theo là \(T\) bộ test.

Mỗi bộ test bao gồm một dòng duy nhất bắt đầu bằng một số nguyên dương \(N\), đại diện cho số lượng nút cần nhấn. Tiếp theo là \(N\) cụm có dạng "\(R_i\) \(P_i\)" trong đó \(R_i\) là màu của rô-bốt (luôn là 'O' hoặc 'B'), và \(P_i\) là vị trí của nút bấm.

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và y là số giây tối thiểu cần thiết để các rô-bốt nhấn các nút đã cho theo đúng thứ tự.

Ràng buộc

\(1 \le P_i \le 100\) với mọi \(i\).

Phân nhóm

• Small dataset (Test set 1 - Visible):
  \(1 \le T \le 20\).
  \(1 \le N \le 10\).

• Large dataset (Test set 2 - Hidden):
  \(1 \le T \le 100\).
  \(1 \le N \le 100\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
4 O 2 B 1 B 2 O 4
3 O 5 O 8 B 100
2 B 2 B 1

Case #1: 6
Case #2: 100
Case #3: 4

Nguồn

Google Code Jam 2011, Vòng loại, bài Bot Trust.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.