Mark I is the first generation robot designed by the corporation for mine exploration. The area to explore is always partitioned into grids. Each grid may or may not have mine underground. The robot's task is to explore the mines in the area.
The robot can perform actions according to the following four instructions:
Forward: The robot will move forward by one grid;
Turn Left: The robot will turn to its left;
Turn Right: The robot will turn to its right;
Scan: The robot will scan the grid in front of itself.
Mark I is so popular that it brings considerable profit to the corporation. However some other companies begin to devise similar products. In order to defeat those opponents, Mark II comes to the world. Since many customers complain about the complexity of the former product, Mark II no long uses the old instructions. Instead it supports only 2 instructions - Move and Scan.
Move instruction is in the following form:
Move DIR N: DIR can be either "Forward", "Back", "Left" or "Right". N is a positive number. It will make the robot move forward by N grids. If DIR is not "Forward", the robot will turn to the specified direction before making the movements.
Scan command is in the following form:
Scan DIR: DIR can be either "Forward", "Back", "Left" or "Right". It will make the robot scan the grid in front of itself. If DIR is not "Forward", the robot will turn to the specified direction before performing the scans.
In order to persuade those original customers with Mark I to upgrade their products, the corporation plans to install a new chip into Mark II, which can translate the old instruction scripts into the equivalent new version.
Input Description
Standard input will contain multiple test cases. The first line of the input is a single integer T (1 <= T <= 10) which is the number of test cases. T test cases follow, each preceded by a single blank line.
Each test case is an old instruction script. It starts with an integer N (1 <= N <= 1,000) which is the number of instructions in the script. The following N lines give the complete script, with one instruction on each line. The area is considered boundless.
Output Description
Results should be directed to standard output. Start each case with "Case #:" on a single line, where # is the case number starting from 1. Two consecutive cases should be separated by a single blank line. No blank line should be produced after the last test case.
For each test case, print the minimum number of instructions in the equivalent new instruction script. The robot must start from the same location and face the same direction, and will scan the same grids in the same order.
Sample Input
1
8
Forward
Forward
Turn Left
Forward
Scan
Turn Right
Scan
Forward
Sample Output
Case 1:
4
HINT: A possible translation would be:
Move Forward 2
Move Left 1
Scan Forward
Scan Right
