Farmer John décide de entourer des parties de sa ferme d’une nouvelle clôture, mais il se laisse sans cesse distraire et obtient une forme bien plus étrange que prévu !

FJ part de $(0,0)$ et fait $N$ pas, chacun d'une unité vers le nord, le sud, l'est ou l'ouest. À chaque pas, il pose derrière lui une unité de clôture. Ainsi, un premier pas au nord crée un segment de $(0,0)$ à $(0,1)$. Il peut revisiter des points plusieurs fois et même poser plusieurs fois le même segment. Si son chemin traverse une clôture déjà posée, celle-ci peut se croiser elle-même.

Une fois terminé, FJ est très déçu du résultat. Il remarque notamment que des régions peuvent être séparées des autres, empêchant d'aller de l'une à l'autre sans franchir une clôture. Il veut y ajouter des portails pour y remédier. On peut en placer sur tout segment construit de longueur unité, permettant de passer entre ses deux côtés.

Déterminez le nombre minimal de portails pour que chaque région soit de nouveau accessible depuis toute autre région.

Entrée

La première ligne contient $N$ ($1 \leq N \leq 1000$). La suivante contient une chaîne de longueur $N$ décrivant le chemin : N (nord), E (est), S (sud) ou W (ouest).

Sortie

Affichez un entier donnant le minimum de portails pour reconnecter complètement toutes les régions. La réponse peut être $0$ si la ferme est déjà connexe.

Exemples

Entrée 1

14
NNNESWWWSSEEEE

Sortie 1

2

Auteur du problème : Brian Dean