Infinite House of Pancakes 刚刚推出了一种新型煎饼！它的一面印有巧克力豆组成的笑脸（“笑脸面”），另一面则什么都没有（“空白面”）。

你是当值的领班，厨房刚刚给了你一叠煎饼要端给顾客。作为一名优秀的煎饼服务员，你拥有“X射线煎饼视觉”，可以看到叠中每一块煎饼是笑脸面朝上还是空白面朝上。你认为如果所有煎饼在端上桌时都是笑脸面朝上，顾客会最开心。

你知道以下操作：小心地从叠顶拿起若干块煎饼（可能是全部），将整组煎饼翻转，然后放回剩余未拿起的煎饼上方。翻转一组煎饼时，你是将整组作为一个整体进行翻转；你不能单独翻转每一块煎饼。形式化地说：如果我们从上到下将煎饼编号为 1, 2, ..., $N$，你选择翻转顶部的 $i$ 块。翻转后，叠的顺序变为 $i, i-1, ..., 2, 1, i+1, i+2, ..., N$。此时，第 1, 2, ..., $i$ 块煎饼的朝向变为相反面，而第 $i+1, i+2, ..., N$ 块煎饼的朝向保持不变。

例如，用 + 表示笑脸面，- 表示空白面。假设从上到下的叠为 --+-。一种有效的操作方式是拿起顶部的三块，翻转整组，然后放回剩下的第四块煎饼上（第四块保持原位且不变）。此时叠的新状态为 -++-。其他有效方式包括拿起并翻转顶部的一块、顶部两块或全部四块。例如，选择并翻转中间两块或底部一块是无效的；你只能从顶部取走若干块。

在所有煎饼都变为笑脸面朝上之前，你不能将它们端给顾客，但你不想让煎饼变凉，所以必须迅速行动！在最优选择下，你需要执行多少次操作才能使所有煎饼都变为笑脸面朝上？

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是 $T$ 个测试用例。每个测试用例由一行字符串 $S$ 组成，每个字符要么是 +（表示初始时笑脸面朝上），要么是 -（表示初始时空白面朝上）。字符串从左到右读取，表示从上到下的煎饼叠。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是使所有煎饼变为笑脸面朝上所需的最少操作次数。

数据范围

$1 \le T \le 100$。 $S$ 中的每个字符均为 + 或 -。

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

$1 \le \text{length of } S \le 10$。

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

$1 \le \text{length of } S \le 100$。

样例

输入 1

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

输出 1

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

说明

在 Case #1 中，你只需要执行一次操作，翻转第一块（也是唯一一块）煎饼。

在 Case #2 中，你只需要执行一次操作，翻转第一块煎饼。

在 Case #3 中，你必须执行两次操作。一种最优解是先翻转第一块煎饼，使叠变为 --，然后翻转两块煎饼，使叠变为 ++。注意，你不能只翻转底部的一块来获得一步解；每次执行操作时，必须选择从顶部开始的一叠。

在 Case #4 中，所有煎饼已经是笑脸面朝上，因此不需要做任何事。

在 Case #5 中，一种有效的解是先翻转整叠煎饼得到 +-++，然后翻转顶部的一块得到 --++，最后翻转顶部的两块得到 ++++。