JASIEK - Jasiek

no tags 

Jasiek is only 6 years old, but he already has many skills. He likes drawing and asking riddles very much. This morning he got a sheet of grid paper and a pencil from his mother and he started drawing. All his drawings have some common properties:

  • Jasiek colors full grid squares;
  • if some coloured grid squares touch each other, it means they have a common edge or a corner;
  • all grid squares are connected, which means between every two coloured grid squares there is a sequence of coloured grid squares, which have a common edge;
  • there are no white holes, that is from every white grid box it is possible to draw a line to the boundary of the sheet which never touches any coloured grid square.

At noon mom phoned and asked what Jasiek's today's picture was. The boy didn't answer directly, but described the picture by a sequence of moves needed to walk around the centres of the coloured squares on its boundary, ie. those squares which have at least one common corner with a white square. Jasiek set the starting square and then gave the sequence of moves necessary to walk along the boundary squares anti-clockwise. Mom was very surprised by the complexity of the picture and especcialy by the number of coloured squares. Given Jasiek's description, can you quickly count how many coloured squares there are in the picture?

Task

Write a program which

  • reads (from standard input) Jasiek's description of the picture,
  • counts the number of coloured squares,
  • writes out the outcome (to standard output).

Input

Ten test cases (given one under another, you have to process all!). Each of the test cases is a series of lines. Each line consists of only one character. The letter P means the beginning of the description. The letter K means the end of the desription (and the test case). All other lines (if any) contain one of the letters N, W, S or E (N meaning North, W - West, S - South and E - East). Every line of the description corresponds to the relative position of the centre of some square on the boundary of the picture. The first and the last line correspond to the same square. A letter in a line other than the first or the last tells you which way you have to go in order to get to the next boundary square when going around the picture anti-clockwise. Jasiek's description finishes after going around the picture once. The length of the description doesn't exceed 20000 letters.

Output

For every testcase your program should write (to the standard output) only one line with one integer, equal to the number of coloured squares in Jasiek's picture.

Example

Example illustration

Input:
P
S
S
S
E
N
E
E
S
E
E
N
N
N
N
S
S
S
W
W
N
N
W
W
W
N
S
K
[and 9 test cases more]

Output:
23
[and 9 test cases more]


hide comments
Aditya Joshi: 2012-11-09 12:52:34

Jaseik creates bitmaps ;)


Added by:Adam Dzedzej
Date:2004-06-09
Time limit:0.440s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Internet Contest Pogromcy Algorytmow (Algorithm Tamers)
Round III, 2003