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