ANARC05I - What is your Logo

no tags 

Imagine a 2D diagram drawn in the following way: Starting at the origin, you're given a sequence of letters which is entirely made of the following four letters 'U', 'D', 'L', and 'R'. A 'U' is an instruction for you to move one unit upward and drawing a segment at the same time. Similarly, 'D' is for moving down, 'L' for left, and 'R' for right.

For example, figure (a) is drawn by giving the sequence 'UURDLL' while figure (b) is the result of 'UURRRDLLLLUURRRDDD' (in both figures, the starting point is identified by a small circle.)

While segments are allowed to intersect, they're not allowed to overlap. In other words, any two segments will have, at most, one point in common. We're interested in knowing the number of closed polygons, not containing any lines inside, in such diagrams. Figure (a), has only one closed polygon while figure (b) has three. Write a program to do exactly that.

Input

Your program will be tested on one or more test cases. Each test case is specified on a separate line. The diagram is specified using a sequence made entirely of (U|D|L|R) and terminated by the letter 'Q'. All letters are capital letters. None of the segments in a test case will overlap.

The end of test cases is identified by the letter 'Q' on a line by itself.

Length of each sequence is smaller than 1000.

Output

For each test case, write the answer on a separate line.

Sample

input
UURDLLQ
UURRRDLLLLUURRRDDDQ
Q

output
1
3

hide comments
Hussain Kara Fallah: 2014-02-06 04:59:13

using gets::WA
using scanf::AC

Shivam Bansal: 2013-06-03 04:26:52

@finisher pls don't spoil other's fun by giving such big hints :)

Mahavir Chopra: 2013-07-16 14:53:01

EDIT : NO SPOILERS

Last edit: 2013-07-16 14:53:18
Rajarshi Sarkar: 2013-01-04 05:53:35

AC :)
nice one .
"closed polygon" explanation should be more .

DivineAtheist: 2012-10-22 08:53:55

nice one.....

a b : 2012-10-21 21:37:22

ahhhhh.....simple one !!!

Inspiron: 2012-06-02 23:41:39

oooooooooo.....i got it

saket diwakar: 2012-02-14 08:25:02

phew....finally got AC...


Added by:psetter
Date:2009-07-05
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ANARC 2005