题目描述

FarmerJohn 打算在他农场的一部分，建设一个围栏。但是因为没有认真做事，建造完成后，围栏变成一个很奇怪的形状。

具体来说，FJ 从 $(0,0)$ 出发，走了 $N$ 步，每步移动一单位（向东、向南、向西或向东）。

他走过的每一步，都会留下一段单位长度的围栏。例如，如果他的第一步向北，他建造一单位从 $(0,0)$ 到 $(0,1)$ 的围栏。

FJ 可能重复到达点多次，他也可能重复建造一段围栏多次。如果他的路径穿过一段已经建成的围栏，他的围栏也有可能会有交叉。

不用说，FJ 看到完成的围栏时，一定很沮丧。特别的，他发现一些区域被围栏封闭起来，从而无法到达。FJ 想在围栏上，安装一些门来解决这个问题。

门可以安装在任意一段单位长度（注：必须是之前走过的某一步）的围栏上，从而可以穿越这段围栏的两侧。

请计算 FJ 最少需要安装多少个门，才能保证农场上任意区域到任意区域都可到达。

输入格式

第一行一个整数 $N$。

第二行包含一个长度为 $N$ 的字符串，描述 FJ 的路径。每个字符为 $\tt N$（北），$\tt E$（东），$\tt S$（南），或 $\tt W$（西）。

输出格式

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

14
NNNESWWWSSEEEE

2

提示

注意，如果农场初始连通，答案就是 $0$。

数据范围

$1\le n\le 1000$。