Farmer John decide di recintare parti della fattoria con una nuova recinzione, ma continua a distrarsi e finisce con una forma molto più strana del previsto!

FJ parte da $(0,0)$ e fa $N$ passi, ognuno di un'unità verso nord, sud, est o ovest. A ogni passo posa un'unità di recinzione dietro di sé. Per esempio, un primo passo a nord crea un segmento da $(0,0)$ a $(0,1)$. Può tornare sui punti più volte e perfino posare più volte lo stesso segmento. Se il percorso attraversa una recinzione già costruita, questa può incrociare se stessa.

Al termine, FJ è molto deluso. In particolare, alcune regioni possono essere separate dalle altre, impedendo di camminare tra esse senza attraversare una recinzione. Vuole aggiungere cancelli per risolvere il problema. Un cancello può essere inserito in qualunque segmento costruito di lunghezza unitaria e consentire il passaggio tra i suoi lati.

Determina il minimo numero di cancelli affinché ogni regione sia nuovamente raggiungibile da qualsiasi altra.

Input

La prima riga contiene $N$ ($1 \leq N \leq 1000$). La seguente contiene una stringa di lunghezza $N$ con il percorso di FJ. Ogni carattere è N (nord), E (est), S (sud) o W (ovest).

Output

Stampa un intero: il minimo di cancelli per ripristinare la connessione completa di tutte le regioni. La risposta può essere $0$ se la fattoria è già connessa.

Esempi

Input 1

14
NNNESWWWSSEEEE

Output 1

2

Autore del problema: Brian Dean