Farmer John decide cercar partes da fazenda com uma nova cerca, mas se distrai continuamente e acaba com uma forma muito mais estranha que a planejada!

FJ começa em $(0,0)$ e dá $N$ passos, cada um de uma unidade para norte, sul, leste ou oeste. A cada passo, coloca uma unidade de cerca atrás de si. Por exemplo, um primeiro passo para norte cria um segmento de $(0,0)$ a $(0,1)$. Pode visitar pontos várias vezes e até colocar o mesmo segmento repetidamente. Se o caminho atravessa uma cerca já construída, ela pode cruzar a si mesma.

Ao terminar, FJ fica muito decepcionado. Em particular, algumas regiões podem ficar separadas das outras, sem ser possível caminhar entre elas sem atravessar uma cerca. Quer adicionar portões para resolver isso. Um portão pode ser colocado em qualquer segmento construído de comprimento unitário, permitindo passar entre seus dois lados.

Determine o mínimo de portões para tornar cada região novamente acessível a partir de qualquer outra.

Entrada

A primeira linha contém $N$ ($1 \leq N \leq 1000$). A seguinte contém uma string de comprimento $N$ que descreve o caminho de FJ. Cada caractere é N (norte), E (leste), S (sul) ou W (oeste).

Saída

Imprima um inteiro: o mínimo de portões para restaurar a conectividade completa de todas as regiões. A resposta pode ser $0$ se a fazenda já for conectada.

Exemplos

Entrada 1

14
NNNESWWWSSEEEE

Saída 1

2

Autor do problema: Brian Dean