Farmer John möchte Teile seiner Farm neu einzäunen, lässt sich aber ständig ablenken und baut am Ende eine viel seltsamere Form als geplant!

FJ beginnt bei $(0,0)$ und macht $N$ Schritte, jeweils eine Entfernungseinheit nach Norden, Süden, Osten oder Westen. Bei jedem Schritt errichtet er hinter sich eine Einheit Zaun. Geht er zuerst nach Norden, entsteht etwa ein Zaunstück von $(0,0)$ bis $(0,1)$. Er kann Punkte mehrmals besuchen und sogar dasselbe Stück mehrmals errichten. Führt sein Weg durch einen bestehenden Zaun, kann dieser sich selbst kreuzen.

Nach Abschluss ist FJ ziemlich enttäuscht. Insbesondere können Bereiche der Farm voneinander getrennt sein, sodass man ohne Zaunquerung nicht zwischen ihnen gehen kann. Tore sollen das beheben. Ein Tor kann in jedem errichteten Zaunstück der Länge eins eingebaut werden und den Durchgang zwischen seinen Seiten ermöglichen.

Bestimme die kleinste Anzahl Tore, damit jeder Bereich wieder von jedem anderen erreichbar ist.

Eingabe

Die erste Zeile enthält $N$ ($1 \leq N \leq 1000$). Die nächste enthält eine Zeichenkette der Länge $N$ mit FJs Weg. Jedes Zeichen ist N (Norden), E (Osten), S (Süden) oder W (Westen).

Ausgabe

Gib eine ganze Zahl aus: die minimale Toranzahl zur vollständigen Verbindung aller Bereiche. Ist die Farm von Anfang an verbunden, kann die Antwort $0$ sein.

Beispiele

Eingabe 1

14
NNNESWWWSSEEEE

Ausgabe 1

2

Aufgabenautor: Brian Dean