Bạn đang học một khóa lập trình được chấm bằng các bộ bài tập thuộc nhiều loại. Khóa học kéo dài một số ngày chẵn dương. Ban đầu bạn không có bộ bài nào. Mỗi ngày, bạn phải làm đúng một việc:

• Yêu cầu một bộ bài “Coding”.
• Yêu cầu một bộ bài “Jamming”.
• Nộp một bộ bài để chấm. Chỉ được chọn việc này nếu đang giữ ít nhất một bộ. Nếu có nhiều bộ, bắt buộc phải nộp bộ được yêu cầu gần đây nhất, bất kể loại nào.

Mọi bộ bài đều khác nhau. Không có yêu cầu về số bộ từng loại phải nộp. Sau khi nộp, bạn không còn giữ bộ đó. Mọi bộ chưa nộp khi khóa học kết thúc đều không đem lại điểm.

Bạn yêu cầu và nộp bài cho một trợ giảng trí tuệ nhân tạo. Kỳ lạ thay, mỗi ngày trợ giảng có một trong hai tâm trạng: “Coding” hoặc “Jamming”.

Khi yêu cầu một bộ bài:

• Nếu chủ đề yêu cầu trùng tâm trạng, trợ giảng giao bộ có điểm tối đa 10.
• Nếu không trùng, trợ giảng giao bộ có điểm tối đa 5.

Khi nộp một bộ bài:

• Nếu chủ đề bộ bài trùng tâm trạng ngày nộp, bạn nhận điểm tối đa của bộ đó.
• Nếu không trùng, bạn nhận ít hơn điểm tối đa 5 điểm.

Ví dụ, nếu xin bộ Coding vào ngày trợ giảng có tâm trạng Coding và nộp vào ngày tâm trạng Jamming, bộ có tối đa 10 nhưng bị trừ 5, nên bạn nhận 5 điểm. Nếu xin bộ Jamming vào ngày tâm trạng Coding rồi nộp vào ngày tâm trạng Jamming, bộ chỉ có tối đa 5 nhưng được nhận trọn 5 điểm.

Nhờ một đồng nghiệp khóa trên hiểu trợ giảng, bạn biết trước tâm trạng mỗi ngày. Tổng điểm lớn nhất có thể đạt là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm một dòng là chuỗi \(S\) chỉ gồm C và J. Ký tự thứ \(i\) mô tả tâm trạng ngày thứ \(i\): C là Coding và J là Jamming.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test, bắt đầu từ 1, và y là số điểm tối đa.

Ràng buộc

• \(1\le T\le100\).
• Độ dài \(S\) là số chẵn.

Phân nhóm

Test Set 1 (Small, hiển thị)

\(2\le |S|\le50\).

Test Set 2 (Large, ẩn)

• \(2\le |S|\le20000\).
• Tổng độ dài mọi chuỗi \(S\) trong bộ dữ liệu không quá 150000.

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

5
CCJJ
CJCJ
CJJC
CJJJ
CCCCCC

Case #1: 20
Case #2: 10
Case #3: 20
Case #4: 15
Case #5: 30

Nguồn

Google Code Jam 2016, Vòng 3, bài Teaching Assistant.

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