You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Background

Special for beginners, ^_^

Description

小C打算在他家里院子的一部分，建设一个围栏。小C从(0,0)出发，走N 步（只能向东、向南、向西或向东，且每步移动一单位），凡是他走过的地方都会建造一个围栏。例如，如果他的第一步向北，他建造一单位从(0,0)到(0,1)的围栏。(坐标可以为负数）

但是因为小C的粗心，他可能重复到达过某个点，他也可能重复建造一段围栏多次，他走过的的路径还可能穿过一段已经建成的围栏，这导致他建造的围栏变成一个很奇怪的形状。

特别糟糕的是，小C发现建造的围栏有很多交叉，导致一些区域被围栏封闭起来，从而无法到达。

为了使得院子里的所有地方都能到达，小C只能通过在围栏上安装门来解决这个问题。门可以安装在任意一段单位长度（注：必须是之前走过的某一步）的围栏上，从而可以穿越这段围栏的两侧。

请计算小C最少需要安装多少个门，才能保证院子上任意区域到任意区域都可到达。

Format

Input

1行：包含N。

2行：包含一个长度为N的字符串，描述小C的路径。每个字符为N（北），E（东），S（南）,或W（西）。

Output

输出一个整数，表示为了保证院子所有区域的连通性，小C最少需要安装多少个门。

Samples

14
NNNESWWWSSEEEE

2

Limitation

注意，如果​院子​初始连通，答案就是0。

对于 20% 的数据，保证 1 ≤ n ≤ 100；

对于100% 的数据，保证 1 ≤ n ≤ 1000；