Description

你正在上一门以题集为评分方式的编程课程。课程持续天数为正偶数天。你开始时没有任何题集。在课程的每一天，你必须执行以下三种操作之一：

• 申请一个“编程（Coding）”题集；
• 申请一个“Jamming”题集；
• 提交一个题集进行评分。你必须至少拥有一个题集才能选择此操作。如果你有多个题集，必须提交最近申请的那一个，无论其类型如何。

所有题集都是不同的。对提交题集的类型和数量没有要求。一旦你提交了某个题集，你就不再拥有该题集。任何在课程结束前未提交的题集都不会获得分数。

题集的申请和提交都通过一个人工智能助教完成。奇怪的是，助教每天都有不同的心情——每一天只会喜欢“Coding”或“Jamming”中的一种。

• 当你申请题集时：
  • 如果申请的题集类型与助教当天的心情一致，则该题集最高可得 10 分。
  • 如果申请的题集类型与助教当天的心情不一致，则该题集最高可得 5 分。
• 当你提交题集时：
  • 如果提交的题集类型与助教当天的心情一致，则你能获得该题集的最高分。
  • 如果提交的题集类型与助教当天的心情不一致，则你获得的分数比最高分少 5 分。

例如：

• 如果你在助教心情为“Coding”的那天申请了一个“Coding”题集，并在助教心情为“Jamming”的那天提交，则你能获得 5 分：该题集最高分为 10 分，但助教会少给 5 分。
• 如果你在助教心情为“Coding”的那天申请了一个“Jamming”题集，并在助教心情为“Jamming”的那天提交，则你能获得 5 分：该题集最高分为 5 分，助教会给你最高分。

幸运的是，你有一位非常了解助教的师兄，他告诉了你课程每一天助教的心情。请问你最多能获得多少分？

Input Format

输入的第一行包含一个整数 $\mathbf{T}$，表示测试用例数量。接下来有 $\mathbf{T}$ 组测试用例，每组一行，包含一个由 $\mathbf{C}$ 和/或 $\mathbf{J}$ 组成的字符串 $\mathbf{S}$。第 $i$ 个字符表示课程第 $i$ 天助教的心情，$\mathbf{C}$ 表示“Coding”，$\mathbf{J}$ 表示“Jamming”。

Output Format

对于每组测试用例，输出一行 Case #x: y，其中 $\mathrm{x}$ 为测试用例编号（从 1 开始），$\mathrm{y}$ 表示你在该组测试用例下能获得的最高分。

5
CCJJ
CJCJ
CJJC
CJJJ
CCCCCC

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

Hint

样例解释

对于样例第 1 组，最优策略如下：

• 第 1 天：申请“Coding”题集（记为 C1）。
• 第 2 天：提交 C1。
• 第 3 天：申请“Jamming”题集（记为 J1）。
• 第 4 天：提交 J1。

对于样例第 2、3、4 组，最优策略为：先申请 C1，再申请 J1，然后提交 J1，最后提交 C1。

以第 2 组为例，注意你不能先申请 C1，再申请 J1，然后提交 C1。因为每次只能提交最近申请的题集。

对于第 5 组，你可以每隔一天申请一个“Coding”题集，下一天就提交它。

限制条件

• $1 \leqslant \mathbf{T} \leqslant 100$。
• $\mathbf{S}$ 的长度为偶数。

小数据集（5 分，测试集 1 - 可见）

• $2 \leqslant \mathbf{S}$ 的长度 $\leqslant 50$。

大数据集（10 分，测试集 2 - 隐藏）

• $2 \leqslant \mathbf{S}$ 的长度 $\leqslant 20000$。
• 所有测试用例的 $\mathbf{S}$ 总长度不超过 150000。

翻译由 GPT4.1 完成。