Farmer John решил огородить части фермы новым забором, но постоянно отвлекался, и форма получилась гораздо страннее задуманной!

FJ начинает в $(0,0)$ и делает $N$ шагов, каждый на единицу расстояния на север, юг, восток или запад. При каждом шаге он оставляет за собой единичный отрезок забора. Например, первый шаг на север создаёт забор от $(0,0)$ до $(0,1)$. Он может многократно посещать точки и даже многократно ставить один и тот же отрезок. Если путь проходит через уже построенный забор, тот может пересекать сам себя.

После завершения FJ весьма огорчён результатом. В частности, некоторые области фермы могут оказаться отделены от других, так что пройти между ними без пересечения забора нельзя. Он хочет исправить это воротами. Ворота можно поставить на любом построенном единичном отрезке, разрешив проход между его сторонами.

Найдите минимальное число ворот, чтобы из каждой области фермы снова можно было попасть в любую другую.

Входные данные

Первая строка содержит $N$ ($1 \leq N \leq 1000$). Следующая — строку длины $N$ с путём FJ. Символы: N (север), E (восток), S (юг) или W (запад).

Выходные данные

Выведите одно целое число — минимум ворот для полной связности всех областей. Если ферма связна изначально, ответ может быть $0$.

Примеры

Входные данные 1

14
NNNESWWWSSEEEE

Выходные данные 1

2

Автор задачи: Brian Dean