Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
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.

Input

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.

Output

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

Sample Input

2
DLULDDRRRUUULD
UUUULLLLDDDDRRRR

Sample Output

case 1: 6
case 2: 16


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