B. A Magical Dance
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Cinderella is at the royal ball, and is asked to perform a special dance. In this dance, she's going to do a total of $$$n$$$ twirls.

After each twirl, Cinderella will be facing a cardinal direction: North, East, South, or West. During a twirl, Cinderella must choose whether to turn 90 degrees clockwise or counterclockwise to face a new direction. She cannot turn any further than this, and she also cannot stay facing the same direction. Cinderella can also start her dance routine in any location.

The direction that Cinderella faces after each twirl is actually very important. For each "state" after her twirls ($$$n$$$ total), Lady Tremaine has a preferred direction for her to face, stored in $$$s_i$$$, the $$$i$$$th character in a string $$$s$$$ of length $$$n$$$. If Cinderella is facing in the correct direction after a twirl, her wicked stepmother will be very pleased. To maximize the effectiveness of her dance routine, Cinderella wants to match her stepmother's requests as many times as possible.

Help Cinderella maximize the effectiveness of her dance.

Input

The first line contains $$$n$$$ $$$(1 \leq n \leq 10^5)$$$, the number of twirls Cinderella will complete.

The next line contains $$$s$$$, a string of length $$$n$$$ storing the directions Lady Tremaine wishes for Cinderella to face, where the preferred direction for the $$$i$$$th $$$(1 \leq i \leq n)$$$ twirl is stored in $$$s_i$$$. All characters in $$$s$$$ will be 'N', 'S', 'W', or 'E', representing the 4 cardinal directions.

Output

Output a single number, the maximum amount of times Cinderella can face in the preferred direction.

Examples
Input
5
EWNSE
Output
3
Input
8
SEENEWWW
Output
4
Note

In the first test case, one sequence of directions Cinderella can face after each of the dance's twirls is:

E -> S -> W -> S -> E

Cinderella will be in the preferred direction in the 1st, 4th, and 5th states. It can be shown that there are no sequences for which Cinderella faces the preferred direction more than 3 times.