植物大战僵尸

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

很多人应该玩过植物大战僵尸的游戏。
这个游戏的目的是在最右边放下可能的僵尸进入被植物保护的在最左边的房子。

为了使这个问题更简单,我们假设只有一种僵尸(zombies),这种僵尸有50 hp(生命值)。
地图只有一行,我们假设只有两种植物:豌豆射手( Peashooter  10 hp)和土豆雷(Potato Mine);
按照如下步骤进行操作(提示:一定要按照下面的操作顺序进行)
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).
现在,给你一个地图,最少需要多少僵尸(zombies)才能侵入最左边的房子。

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

Hint

 

Source

WL