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 javafx.util.Pair;

import java.util.*;
import java.io.*;
import java.text.*;
import java.math.*;

public class Main {
    public static FastIO file = new FastIO();

    private static void solve() {
        int amount = nextInt();
        while (amount-- > 0) {
            HashSet<Pair<Pair<Integer, Integer>, Integer>> set = new HashSet<>();
            int x = 0, y = 0, answer = 0, local = 0;
            char[] arr = nextLine().toCharArray();
            for (int i = 0; i < arr.length; i++) {
                Pair<Integer, Integer> first = new Pair<>(x, y);
                switch (arr[i]) {
                    case 'N':
                        y++;
                        local = 1;
                        break;
                    case 'S':
                        y--;
                        local = 2;
                        break;
                    case 'W':
                        x--;
                        local = 3;
                        break;
                    case 'E':
                        x++;
                        local = 4;
                        break;
                }
                Pair<Pair<Integer, Integer>, Integer> pair1 = new Pair<>(first, local);
                Pair<Integer, Integer> second = new Pair<>(x, y);
                switch (local) {
                    case 1:
                        local = 2;
                        break;
                    case 2:
                        local = 1;
                        break;
                    case 3:
                        local = 4;
                        break;
                    case 4:
                        local = 3;
                        break;
                }
                Pair<Pair<Integer, Integer>, Integer> pair2 = new Pair<>(second, local);
                if (set.contains(pair1) || set.contains(pair2) ) answer++;
                else {
                    set.add(pair1);
                    answer += 5;
                }
            }
            System.out.println(answer);
        }
    }

    private static int[] nextArray(int n) {
        int[] a = new int[n];
        for (int i = 0; i < n; i++) a[i] = nextInt();
        return a;
    }

    public static int[][] nextArray2D(int n, int m) {
        int[][] result = new int[n][];
        for (int i = 0; i < n; i++) {
            result[i] = nextArray(m);
        }
        return result;
    }

    public static long pow(long n, long p) {
        long ret = 1L;
        while (p > 0) {
            if (p % 2 != 0L)
                ret *= n;
            n *= n;
            p >>= 1L;
        }
        return ret;
    }

    public static String next() {
        return file.next();
    }

    public static int nextInt() {
        return file.nextInt();
    }

    public static long nextLong() {
        return file.nextLong();
    }

    public static double nextDouble() {
        return file.nextDouble();
    }

    public static String nextLine() {
        return file.nextLine();
    }

    public static class FastIO {
        BufferedReader br;
        StringTokenizer st;
        PrintWriter out;

        public FastIO() {
            br = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        }

        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;
        }
    }

    public static void main(String[] args) throws IOException {
        solve();
    }


}

