Farmer John은 농장의 일부를 둘러싸는 새 울타리를 짓기로 했지만, 자꾸 주의가 흐트러져 계획보다 훨씬 이상한 모양을 만들었습니다!

FJ는 $(0,0)$에서 시작해 $N$걸음을 걷고, 매번 북쪽, 남쪽, 동쪽 또는 서쪽으로 거리 한 단위 이동하며 뒤에 길이 한 단위의 울타리를 놓습니다. 예를 들어 첫걸음이 북쪽이면 $(0,0)$부터 $(0,1)$까지 울타리를 만듭니다. 같은 점을 여러 번 방문하고 같은 울타리 구간을 여러 번 놓을 수도 있습니다. 이미 지은 울타리를 가로지르는 경로라면 울타리가 자기 자신과 교차할 수도 있습니다.

완성 후 FJ는 결과에 매우 실망합니다. 특히 농장 일부 지역이 다른 지역과 분리되어 울타리를 건너지 않고는 서로 걸어갈 수 없을 수 있습니다. 이를 해결하려고 문을 추가하려 합니다. 지은 길이 한 단위의 어느 울타리 구간에나 문을 달아 양쪽 사이로 통행할 수 있게 할 수 있습니다.

농장의 모든 지역이 다시 다른 모든 지역에서 도달 가능하도록 필요한 문의 최소 개수를 구하세요.

입력

첫째 줄은 $N$ ($1 \leq N \leq 1000$)입니다. 다음 줄은 FJ의 경로를 나타내는 길이 $N$의 문자열입니다. 각 문자는 N (북), E (동), S (남), W (서) 중 하나입니다.

출력

모든 지역의 완전한 연결을 복원하는 최소 문 개수를 정수 하나로 출력하세요. 처음부터 연결되어 있다면 답이 $0$일 수도 있습니다.

예제

입력 1

14
NNNESWWWSSEEEE

출력 1

2

문제 작성자: Brian Dean