Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3107
Counting Squares

Time Limit: 1 Second      Memory Limit: 32768 KB

Nancy is the best babysitter of the block and today she faces her greater challenge: little John and his anxious box of markers. But Nancy has prepared herself for this eventuality with an activity that it will maintain occupied little John. In a paper sheet with squares John will have to put his blue marker in some corner of a square and at the order of "right" (or left, or up or down) he will have to be draw a segment that unites the present position with next point to its right (or left, or up, or down); the marker will be placed in that last point hoping the following instruction.

The idea is that John follows the instructions, draws a simple polygon and counts the number of squares that are within the figure. Remember that the boundary of a simple polygon does not cross itself.


In the first line is a integer number n, that represents the number of tests. In following n lines there will be a statement containing the instructions: U - up, D - down, R - right, L - left. The length of the statement will less than 100.


For each test it's necessary to indicate the number of squares that the polygon contains.

Sample Input


Sample Output

case 1: 6
case 2: 16

Source: The 2007 ACM Mexico and Central America Programming Contest
Submit    Status