Farmer John מחליט לבנות גדר חדשה סביב חלקים מחוותו, אך דעתו מוסחת שוב ושוב, והצורה יוצאת מוזרה הרבה יותר מכפי שהתכוון!

FJ מתחיל ב־$(0,0)$ ועושה $N$ צעדים, כל אחד יחידת מרחק צפונה, דרומה, מזרחה או מערבה. בכל צעד הוא מניח מאחוריו יחידת גדר. למשל צעד ראשון צפונה יוצר קטע מ־$(0,0)$ עד $(0,1)$. הוא עשוי לבקר בנקודות פעמים רבות ואף להניח את אותו קטע שוב ושוב. אם המסלול חוצה גדר שכבר נבנתה, הגדר עשויה לחצות את עצמה.

בסיום FJ מאוכזב מאוד. בפרט, ייתכן שאזורים בחווה הופרדו מאחרים, כך שאי אפשר ללכת ביניהם בלי לחצות גדר. הוא רוצה להוסיף שערים כדי לתקן זאת. ניתן להוסיף שער לכל קטע גדר שנבנה באורך יחידה, ולאפשר מעבר בין שני צדדיו.

מצאו את מספר השערים המזערי שיאפשר להגיע שוב מכל אזור בחווה לכל אזור אחר.

קלט

השורה הראשונה מכילה $N$ ($1 \leq N \leq 1000$). הבאה מכילה מחרוזת באורך $N$ המתארת את מסלול FJ. כל תו הוא N (צפון), E (מזרח), S (דרום) או W (מערב).

פלט

הדפיסו שלם אחד: מספר השערים המזערי להחזרת קישוריות מלאה לכל האזורים. התשובה עשויה להיות $0$ אם החווה הייתה קשירה מלכתחילה.

דוגמאות

קלט 1

14
NNNESWWWSSEEEE

פלט 1

2

מחבר הבעיה: Brian Dean