Problem Description
The "endless" model in "I, zombie" of "Plants vs. Zombies" is my favourite.
The aim of the game is to put down the zombies most reasonable in the right-most , to eat the brain protected by Plants in the left-most.
To simplify the problem ,we provide only one kind of Zombies : normal Zombies with 50 hp each.
The map contains one row only, and we provide two kinds of plants : Peashooter (with 10hp) and Potato Mine.
The operating steps of every second are as below(Warning: make sure your program strictly follow the order of these steps):
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).
Now, given the map, you are to tell me how many zombies are needed at least, in order to eat the brain in the left-most?
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
