Description

无限煎饼屋刚刚推出了一种新型煎饼！煎饼的一面用巧克力豆装饰成了笑脸（称为“开心面”），另一面则什么都没有（称为“空白面”）。

你是当班的首席服务员，厨房刚刚给你一摞煎饼，准备让你端给顾客。作为一名优秀的煎饼服务员，你拥有 X 光煎饼视力，可以看清堆中每一张煎饼朝上的是开心面还是空白面。你认为如果每一张煎饼在端给顾客时都是开心面朝上，顾客会最开心。

你掌握如下操作：小心地从煎饼堆顶取出若干张（可能全部），将这一组整体翻面，然后再放回剩下的煎饼上方。翻动一组煎饼时，整个组会被整体翻转，而不是单独翻转每一张。形式化地说：如果我们将煎饼从上到下编号为 $1,2,\ldots,N$，你可以选择翻转最上面的 $i$ 张。翻转后，堆的顺序变为 $i,i-1,\ldots,2,1,i+1,i+2,\ldots,N$。编号 $1,2,\ldots,i$ 的煎饼现在朝上的面会变成原来的反面，而 $i+1,i+2,\ldots,N$ 的煎饼则保持原状。

例如，我们用 + 表示开心面朝上，用 - 表示空白面朝上。假设从顶到底的煎饼堆为 --+-。一种可行操作是取出最上面的三张，整体翻转后放回剩下的第四张上方（第四张保持不变）。此时堆的新状态为 -++-。其他合法操作包括只翻最上面的一张、最上面两张或全部四张。不合法的操作包括只翻中间两张或只翻最底下一张，因为你只能从顶部开始取若干张。

只有当所有煎饼都是开心面朝上时，你才会端给顾客，但你不想让煎饼变冷，所以你必须尽快行动！请问，要让所有煎饼都变为开心面朝上，最少需要执行多少次上述操作？

Input Format

输入的第一行包含一个整数 $\mathrm{T}$，表示测试用例数量。接下来有 $\mathrm{T}$ 组测试用例。每组测试用例包含一行字符串 $\mathbf{S}$，其中每个字符为 +（表示该煎饼初始时为开心面朝上）或 -（表示该煎饼初始时为空白面朝上）。从左到右读字符串，表示从堆顶到底的煎饼顺序。

Output Format

对于每组测试用例，输出一行 Case #x: y，其中 $x$ 表示测试用例编号（从 1 开始），$y$ 表示将所有煎饼翻为开心面朝上所需的最小操作次数。

5
-
-+
+-
+++
--+-

Case #1: 1
Case #2: 1
Case #3: 2
Case #4: 0
Case #5: 3

Hint

样例解释

在第 1 组中，你只需操作一次，翻转唯一的一张煎饼。

在第 2 组中，你只需操作一次，只翻转最上面的一张煎饼。

在第 3 组中，你需要操作两次。最优解是先翻转最上面的一张，使堆变为 --，然后再翻转全部两张，使堆变为 ++。注意你不能只翻最下面的一张来一步达成目标；每次操作都必须从顶部开始取连续若干张。

在第 4 组中，所有煎饼已经全部开心面朝上，无需任何操作。

在第 5 组中，一种可行方案是：先翻转全部煎饼，得到 +-++，再翻转最上面一张，得到 --++，最后翻转最上面两张，得到 ++++。

限制条件

• $1 \leqslant \mathrm{T} \leqslant 100$。
• $\mathbf{S}$ 中每个字符均为 + 或 -。

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

• $1 \leqslant$ $\mathbf{S}$ 的长度 $\leqslant 10$。

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

• $1 \leqslant$ $\mathbf{S}$ 的长度 $\leqslant 100$。

翻译由 GPT4.1 完成。