What's Your Logo?

Time limit1sMemory limit128 MB

Summary

Count the empty closed regions formed by a rectilinear path traced by U, D, L, R moves that may cross but never overlap.

Level: Medium7 of 10
Topics: Geometry, BFS, Implementation
Solved: No attempts yet

Problem

Consider a 2D figure drawn as follows. Starting at the origin, you are given a string made up entirely of the four letters U, D, L, and R. A U tells you to move one unit upward while drawing a segment along the way; likewise D moves down, L moves left, and R moves right. For example, figure (a) is drawn from the string UURDLL, while figure (b) is the result of UURRRDLLLLUURRRDDD. (In both figures, the starting point is marked by a small circle.)

Segments may cross one another, but they may never overlap; that is, any two segments share at most one point. We want to count the number of closed polygons that do not contain any segment inside them. Figure (a) has exactly one such closed polygon, while figure (b) has three. Write a program that computes this count.

Input

The input consists of one or more test cases, each on its own line. A figure is given as a string made entirely of the letters U, D, L, R, terminated by the letter Q. All letters are uppercase. No two segments in a test case overlap. The end of input is marked by a line containing only the letter Q.

Output

For each test case, print the answer on its own line.

Examples3

Example 1
Input
```
UURDLLQ
UURRRDLLLLUURRRDDDQ
Q
```
Expected output
```
1
3
```
Example 2
Input
```
URDLQ
Q
```
Expected output
```
1
```
Example 3
Input
```
URQ
Q
```
Expected output
```
0
```