Farmer John quyết định xây một hàng rào mới quanh một số phần của trang trại, nhưng ông liên tục bị xao nhãng và cuối cùng xây hàng rào thành một hình dạng kỳ lạ hơn nhiều so với dự định!

Cụ thể, FJ bắt đầu tại vị trí \((0,0)\) và đi \(N\) bước, mỗi bước di chuyển một đơn vị về phía bắc, nam, đông hoặc tây. Với mỗi bước đi, ông để lại phía sau một đoạn hàng rào dài một đơn vị. Chẳng hạn, nếu bước đầu tiên đi về phía bắc, ông thêm một đoạn hàng rào từ \((0,0)\) đến \((0,1)\). FJ có thể ghé lại một điểm nhiều lần và thậm chí có thể dựng cùng một đoạn hàng rào nhiều lần. Hàng rào còn có thể tự cắt nếu đường đi của ông băng qua một dải hàng rào đã dựng trước đó.

Không cần phải nói, FJ khá thất vọng với kết quả sau khi hoàn tất hàng rào. Đặc biệt, ông nhận thấy mình có thể đã ngăn cách một số khu vực của trang trại với những khu vực khác, khiến người ta không còn có thể đi từ khu vực này sang khu vực kia mà không băng qua hàng rào. FJ muốn thêm các cổng vào hàng rào để khắc phục vấn đề. Một cổng có thể được thêm vào bất kỳ đoạn hàng rào dài một đơn vị nào ông đã dựng, cho phép đi qua giữa hai phía của đoạn đó.

Hãy xác định số cổng ít nhất FJ cần xây để mọi khu vực của trang trại lại có thể đi đến nhau.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) (\(1\le N\le1000\)). Dòng tiếp theo chứa một xâu độ dài \(N\) mô tả đường đi của 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 cho biết số cổng ít nhất FJ cần xây để khôi phục khả năng kết nối hoàn toàn giữa mọi khu vực trong trang trại. Lưu ý rằng đáp án có thể bằng 0 nếu ngay từ đầu mọi khu vực của trang trại đã liên thông.

Ví dụ

14
NNNESWWWSSEEEE

2

Nguồn

USACO 2016 January Contest, Silver - Build Gates: https://usaco.org/index.php?page=viewproblem2&cpid=596

Tác giả: Brian Dean.