Skier rides on a snowy field. Its movements can be described by a string of characters 'S', 'N', 'W', 'E' (which correspond to 1 meter movement in the south, north, west or east direction respectively).

It is known that if he moves along a previously unvisited segment of a path (i.e. this segment of the path is visited the first time), then the time of such movement is 5 seconds. If he rolls along previously visited segment of a path (i.e., this segment of the path has been covered by his path before), then it takes 1 second.

Find the skier's time to roll all the path.

Input

The first line contains an integer t (1 ≤ t ≤ 10^4) — the number of test cases in the input. Then t test cases follow.

Each set is given by one nonempty string of the characters 'S', 'N', 'W', 'E'. The length of the string does not exceed 10^5 characters.

The sum of the lengths of t given lines over all test cases in the input does not exceed 10^5.

Output

For each test case, print the desired path time in seconds.

Example

Input


5
NNN
NS
WWEN
WWEE
NWNWS


Output


15
6
16
12
25
import java.io.*;
import java.util.*;
import java.lang.*;

public class c1 {
    public static void main(String[] args) {
        MyScanner scan = new MyScanner();
        out = new PrintWriter(new BufferedOutputStream(System.out));

        int t=scan.nextInt();
        while(t-->0) {

            String[] s=scan.nextLine().split("");
            Set<String> h=new HashSet<String>();
            int n=0,m=0,ln=0,lm=0;
            int time=0;
            h.add(ln+" "+lm+" "+n+" "+m);
            h.add(n+" "+m+" "+ln+" "+lm);
            for(int c=0;c<s.length;c++) {
                ln=n;
                lm=m;
                if(s[c].equals("N")) {
                    n++;
                } else if(s[c].equals("S")) {
                    n--;
                } else if(s[c].equals("W")) {
                    m--;
                } else {
                    m++;
                }
                if(h.contains(ln+" "+lm+" "+n+" "+m)||h.contains(n+" "+m+" "+ln+" "+lm)) {
                    time++;
                } else {
                    if(!h.contains(ln+" "+lm+" "+n+" "+m))
                    h.add(ln+" "+lm+" "+n+" "+m);
                    if(!h.contains(n+" "+m+" "+ln+" "+lm))
                        h.add(n+" "+m+" "+ln+" "+lm);
                    time+=5;
                }
            }
            out.println(time);
        }
        out.close();
    }
    //node
    static class Node implements Comparable<Node> {
        public int x,y;
        public Node(int x,int y) {
            this.x=x;
            this.y=y;
        }

        public int compareTo(Node other) {
            if(this.x==other.x&&this.y==other.y) return 0;
            else if(this.x>other.x||this.y>other.y) return 1;
            else return -1;
        }

        public boolean equals(Object other) {
            if(other instanceof Node) {
                Node e =(Node)other;
                return this.x==e.x&&this.y==e.y;
            }
            else return false;
        }
    }

    //util
    public static int gcd(int a, int b) {
        if (b == 0)
            return a;
        if (a == 0)
            return b;
        return (a > b) ? gcd(a % b, b) : gcd(a, b % a);
    }

    static ArrayList<Integer> getFactor(int n) {
        ArrayList<Integer> div = new ArrayList<Integer>();
        for (int i=1;i*i<=n;i++) {
            if (n%i==0&&i%2!=0) {
                div.add(i);
            }
        }
        return div;
    }

    public static int lcm(int a, int b) {
        return a * b / gcd(a, b);
    }

    public static boolean isprime(int a) {
        if (a == 0 || a == 1) {
            return false;
        }
        if (a == 2) {
            return true;
        }
        for (int i = 2; i < Math.sqrt(a) + 1; i++) {
            if (a % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static ArrayList<Integer> divisors(int n) {
        ArrayList<Integer> div = new ArrayList<Integer>();
        for (int i=1;i*i<=n;i++) {
            if (n%i==0) {
                div.add(i);
                if (n/i!=i)
                    div.add(n/i);
            }
        }
        return div;
    }

    //scanner
    public static PrintWriter out;

    public static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        public MyScanner() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}