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.*;
/*
* @author Tran Anh Tai
*
 */ 
public class Skier {
    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        Task task = new Task();
        task.solve(in, out);
        out.close();
    }
    private static class Task {
        public void solve(InputReader in, PrintWriter out) {
            int t = in.nextInt();
            for(int j = 0; j < t; j++){
                String s = in.nextToken();
                int l = s.length();
                int cnt = 0;
                // bit mask and hashmap
                Map<Pair, Integer> map = new HashMap();
                int y = 0, x = 0;
                for (int i = 0; i < l; i++){
                    char ch = s.charAt(i);
                    Pair src = new Pair(y, x);
                    int state = map.getOrDefault(src, 0);
                    int mask = 0;
                    if (ch == 'N'){
                        mask = 0;
                        y++;
                    }
                    else if (ch == 'S'){
                        mask = 3;
                        y--;
                    }
                    else if (ch == 'W'){
                        mask = 2;
                        x++;
                    }
                    else{
                        mask = 1;
                        x--;
                    }
                    Pair dest = new Pair(y, x);
                    // put src and dest new state to hash map;
                    map.put(src, state | (1 << mask));
                    int val = map.getOrDefault(dest, 0);
                    if (val == 0 || (val & (1 << (3 - mask))) == 0){
                        cnt += 5;
                    }
                    else{
                        cnt += 1;
                    }
                    map.put(dest, val | (1 << (3 - mask)));
                }
                out.println(cnt);
            }
        }
    }
    static class Pair{
        public int x, y;
        public Pair(int x, int y){
            this.x = x; this.y = y;
        }

        @Override
        public boolean equals(Object obj) {
            return this.x == ((Pair)obj).x && this.y == ((Pair)obj).y;
        }

        @Override
        public int hashCode() {
            return this.x * 100+ this.y;
        }
    }
    // fast input reader class;
    static class InputReader {
        BufferedReader br;
        StringTokenizer st;

        public InputReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream));
        }

        public String nextToken() {
            while (st == null || !st.hasMoreTokens()) {
                String line = null;
                try {
                    line = br.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
                if (line == null) {
                    return null;
                }
                st = new StringTokenizer(line);
            }
            return st.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextToken());
        }
        public long nextLong(){
            return Long.parseLong(nextToken());
        }
    }
}
