Build Gates

Farmer John decided to build a new fence around part of his farm. He kept getting distracted while walking, so the fence came out in a much stranger shape than he planned.

John starts at $(0, 0)$ and takes $N$ steps. Each step moves him one unit north, south, east, or west, and behind every step he leaves one unit of fence. If his first step is north, he adds a fence segment from $(0, 0)$ to $(0, 1)$. He may visit the same point several times, and he may lay a fence on the same segment several times. His path may also cut straight through fence he has already built.

Once the fence is done, John notices that it may have separated parts of the farm from each other, so that walking from one region to another means crossing a fence. He wants to fix this by adding gates. A gate goes on any unit length segment of fence he built, and it lets you pass between the two sides of that segment.

Find the minimum number of gates John needs so that every region of the farm can be reached from every other region.

The first line contains $N$ ($1 \le N \le 1000$).

The second line contains a string of length $N$ describing John's path. Each character is N (north), E (east), S (south), or W (west).

Print one integer, the minimum number of gates John needs to make the whole farm connected again. The answer is 0 when the farm is already connected.