Побудова воріт
Фермер Джон будує огорожу.
Фермер Джон починає з позиції (0, 0) і робить n кроків, кожного разу переміщуючись на одиницю відстані на північ, південь, схід або захід. Кожен раз, коли він робить крок, він будує огорожу за собою. Наприклад, якщо його перший крок буде на північ, він додасть сегмент огорожі від (0, 0) до (0, 1). Фермер Джон може відвідувати ті самі точки багато разів і навіть будувати ті самі відрізки огорожі кілька разів. Його огорожа може навіть перетинати саму себе багато разів.
В результаті, фермер Джон може розділити свою ферму на кілька незалежних огороджених ділянок. Він хоче встановити двері, щоб виправити цю ситуацію. Двері можуть бути встановлені на будь-якому відрізку одиничної довжини, щоб дозволити прохід між двома сторонами цього відрізка.
Визначте мінімальну кількість дверей, які потрібно встановити, щоб кожен регіон був доступний з кожного іншого регіону.
Вхідні дані
Перша строка містить n (1 ≤ n ≤ 1000). Наступна строка містить рядок довжини n, що описує шлях фермера Джона. Кожен символ є одним з N (північ), E (схід), S (південь), W (захід).
Вихідні дані
Виведіть мінімальну кількість дверей, які фермер Джон повинен встановити, щоб відновити повну зв'язність усіх регіонів своєї ферми. Зазначимо, що відповідь може бути 0, якщо ферма спочатку зв'язна.