Breakfast at the Hostel


Submit solution

Points: 100
Time limit: 2.0s
Memory limit: 256M

Author:
Problem type

A youth hostel in Puerto Rico serves a stack of pancakes. The stack is described from top to bottom by a string of signs. A + means that pancake is facing the right way; a - means it is upside down.

In one operation, take one or more pancakes from the top and flip the entire block. This reverses both the order of the selected pancakes and the sign of each one. The rest stay unchanged.

Find the minimum number of operations that makes every sign +.

Input

The first line contains T. Each of the next T lines contains a string S of + and - signs.

Output

For each case i, starting at 1, print exactly "Case #i: answer", without quotation marks.

Constraints

1 ≤ T ≤ 100; 1 ≤ length of S ≤ 100. These are the original large-dataset limits.

Ejemplo
Entrada de Ejemplo Salida de Ejemplo
4
+
--
+-
-+-
Case #1: 0
Case #2: 1
Case #3: 2
Case #4: 3

Flipping the entire stack -- turns it into ++ in one operation.

Source

Adapted for OiPR 2026. Google Code Jam 2016, Qualification Round — Revenge of the Pancakes.


Comments

There are no comments at the moment.