Farmer John quyết định dựng hàng rào mới quanh một số phần trang trại, nhưng cứ mất tập trung nên tạo ra hình dạng kỳ lạ hơn nhiều so với dự định!

FJ bắt đầu ở $(0,0)$ và đi $N$ bước, mỗi bước một đơn vị về bắc, nam, đông hoặc tây. Mỗi bước anh đặt một đơn vị hàng rào sau lưng. Ví dụ bước đầu về bắc tạo đoạn từ $(0,0)$ đến $(0,1)$. Anh có thể thăm lại điểm nhiều lần và thậm chí dựng lại cùng đoạn nhiều lần. Hàng rào có thể tự cắt nếu đường đi xuyên qua hàng rào đã dựng.

Khi xong, FJ rất thất vọng. Đặc biệt, một số vùng có thể bị tách khỏi vùng khác, không thể đi bộ giữa chúng nếu không băng qua hàng rào. Anh muốn thêm cổng để khắc phục. Có thể đặt cổng trên bất kỳ đoạn đã dựng dài một đơn vị, cho phép đi qua giữa hai phía.

Hãy tìm số cổng ít nhất để mỗi vùng trang trại lại đi tới được từ mọi vùng khác.

Dữ liệu vào

Dòng đầu chứa $N$ ($1 \leq N \leq 1000$). Dòng tiếp theo là chuỗi dài $N$ mô tả đường đi FJ. Mỗi ký tự là N (bắc), E (đông), S (nam), hoặc W (tây).

Dữ liệu ra

In một số nguyên: số cổng ít nhất để khôi phục kết nối đầy đủ giữa mọi vùng. Đáp án có thể là $0$ nếu trang trại đã kết nối từ đầu.

Ví dụ

Dữ liệu vào 1

14
NNNESWWWSSEEEE

Dữ liệu ra 1

2

Tác giả bài toán: Brian Dean