### 植物大战僵尸

Time Limit: 1000 ms Memory Limit: 65536 KiB

#### Problem Description

1.Put some or none zombies in the right-most grid one by one. (In the right grid of the right-most plant at beginning).
2.Judge every survived zombie, whether he's standing on a grid with a Peashooter.
2.1.If it's true, he attacks the Peashooter in his grid, and the Peashooter decreases 1 hp. The Peashooter's hp may be negative at that moment, but it's still alive!
2.2.If it's false, he moves left for one grid.
3.If there are still some zombies in the map, every survived Peashooter will shoot a pea to the zombie who was put earliest. (the zombie's hp decreases 1 hp for each pea, the zombie's hp can be negative at that moment, but it's still alive!)
4.If there are zombies in the grids where Potato Mine stands , then the Potato Mine explodes , all the zombies' hp in this grid become 0.
5.The plants and zombies with non-positive hp disappear(until now they are dead).

#### Input

The first line is a number T (1<=T<=100), represents the number of cases.
The next T line with n(0<n<=100) characters ,represents each case ,'P' represents Peashooters ,'M' represents Potato Mine ,no other character in the input.

#### Output

Output a number represents the minimum zombies needed to eat the brain in the left-most.Following the case number (start with 1).

#### Sample Input

5
PM
PP
PPP
MMMMM
PPMM

#### Sample Output

Case 1: 2
Case 2: 1
Case 3: 2
Case 4: 6
Case 5: 3

WL