Roland là một giáo viên toán trung học. Mỗi ngày, ông nhận được hàng trăm bài kiểm tra từ học sinh của mình. Với mỗi bài, ông cẩn thận chọn một điểm chữ cái: 'A', 'B' hoặc 'C'. (Học sinh của Roland quá thông minh để nhận các điểm thấp hơn như 'D' hay 'F'). Sau khi các điểm số đã được quyết định, Roland chuyển các bài kiểm tra cho trợ lý của mình - chính là bạn. Công việc của bạn là đóng dấu điểm số chính xác lên mỗi tờ giấy.

Bạn có một con dấu chữ cái công nghệ thấp nhưng vẫn hoạt động tốt. Để in một chữ cái, bạn gắn một tấm khuôn đặc biệt tương ứng với chữ cái đó vào mặt trước của con dấu, nhúng nó vào mực, rồi đóng lên giấy.

Điều thú vị là thay vì tháo tấm khuôn ra khi bạn muốn đổi chữ cái, bạn có thể chỉ cần đặt một tấm khuôn mới lên trên tấm khuôn cũ. Thực tế, bạn có thể coi các tấm khuôn trên con dấu như một ngăn xếp (stack), hỗ trợ các thao tác sau:

• Push một chữ cái vào đỉnh ngăn xếp. (Tương ứng với việc gắn một tấm khuôn mới vào mặt trước con dấu.)
• Pop một chữ cái khỏi đỉnh ngăn xếp. (Tương ứng với việc tháo tấm khuôn ở mặt trước con dấu.)
• Print chữ cái ở đỉnh ngăn xếp. (Tương ứng với việc thực sự sử dụng con dấu.) Tất nhiên, ngăn xếp phải có ít nhất một chữ cái để thực hiện việc này.

Cho một chuỗi các điểm chữ cái ('A', 'B', và 'C'), bạn cần bao nhiêu thao tác để in toàn bộ chuỗi theo đúng thứ tự? Ngăn xếp ban đầu trống, và bạn phải để ngăn xếp trống khi hoàn thành. Tuy nhiên, bạn có nguồn cung cấp không giới hạn cho mỗi loại khuôn chữ cái để sử dụng trong quá trình thực hiện.

Ví dụ, nếu bạn muốn in chuỗi "ABCCBA", bạn có thể thực hiện trong 12 thao tác như bảng dưới đây:

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào chứa số lượng bộ test, T. T bộ test tiếp theo, mỗi bộ trên một dòng. Mỗi dòng chứa một chuỗi duy nhất S, đại diện cho chuỗi các ký tự mà bạn muốn in ra theo thứ tự.

Dữ liệu ra

Với mỗi bộ test, hãy xuất một dòng chứa "Case #x: N", trong đó x là số thứ tự bộ test (bắt đầu từ 1) và N là số lượng thao tác ngăn xếp tối thiểu cần thiết để in ra S.

Ràng buộc

• S là một chuỗi không rỗng chỉ chứa các chữ cái 'A', 'B', và 'C'.

Phân nhóm

• Small dataset (Test set 1 - Visible):
  • 1 ≤ T ≤ 100.
  • S có tối đa 100 ký tự.
• Large dataset (Test set 2 - Hidden):
  • 1 ≤ T ≤ 20.
  • S có tối đa 7000 ký tự.

Đ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ụ

2
ABCCBA
AAABAAB

Case #1: 12
Case #2: 13

Nguồn

Google Code Jam 2010, Chung kết thế giới, bài Letter Stamper.

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