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
/*
 * Author: pranay.agra
 * Time: 2020-05-07 10:17:16
*/

import java.io.*;
import java.util.*;

public class c {
    public static void main(String[] args) throws IOException {
        Scanner std = new Scanner(System.in);
        BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder strBu = new StringBuilder();
        MergeSort merge = new MergeSort();      

        int t = std.nextInt();
        while (t-- > 0) {
            HashSet<String> coords = new HashSet<>();
            int x = 0;
            int y = 0;
            long cost = 0;
           // coords.add(x + " " + y);
            char[] movement = std.nextLine().toCharArray();
            for (int i = 0; i < movement.length; i++) {
                String pos_before = x + " " + y;
                if (movement[i] == 'N') {
                    y++;
                } else if (movement[i] == 'S') {
                    y--;
                } else if (movement[i] == 'W') {
                    x--;
                } else { //E
                    x++;
                }
                String pos_after = x + " " + y;
                String try1 = pos_before + ":" + pos_after;
                String try2 = pos_after + ":" + pos_before;
                //System.out.println(pos);
                if (coords.contains(try1) || coords.contains(try2)) {
                    cost += 1L;
                } else {
                    coords.add(try1);
                    coords.add(try2);
                    cost += 5L;
                }
            }
            log.write(cost + "\n");
        }
        log.flush();

	

    }

/**
Remember to check for overflow (long)
Does number need to be greater than a lower bound?
**/

    static class Scanner {
        StringTokenizer st;
        BufferedReader br;

        public Scanner(InputStream system) {
            br = new BufferedReader(new InputStreamReader(system));
        }

        public Scanner(String file) throws Exception {
            br = new BufferedReader(new FileReader(file));
        }

        public String next() throws IOException {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(br.readLine());
            return st.nextToken();
        }

        public String nextLine() throws IOException {
            return br.readLine();
        }

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

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

        public char nextChar() throws IOException {
            return next().charAt(0);
        }

        public Long nextLong() throws IOException {
            return Long.parseLong(next());
        }

        public int[] nextArrInt(int n) throws IOException {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public long[] nextArrLong(int n) throws IOException {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }

        public boolean ready() throws IOException {
            return br.ready();
        }

        public void waitForInput() throws InterruptedException {
            Thread.sleep(3000);
        }
    }

    static class MergeSort {
        private void merge(int arr[], int l, int m, int r) {
            int n1 = m - l + 1;
            int n2 = r - m;

            int L[] = new int[n1];
            int R[] = new int[n2];

            for (int i = 0; i < n1; ++i)
                L[i] = arr[l + i];
            for (int j = 0; j < n2; ++j)
                R[j] = arr[m + 1 + j];

            int i = 0, j = 0;

            int k = l;
            while (i < n1 && j < n2) {
                if (L[i] <= R[j]) {
                    arr[k] = L[i];
                    i++;
                } else {
                    arr[k] = R[j];
                    j++;
                }
                k++;
            }
            while (i < n1) {
                arr[k] = L[i];
                i++;
                k++;
            }
            while (j < n2) {
                arr[k] = R[j];
                j++;
                k++;
            }
        }

        void sort(int arr[]) {
            lensort(arr, 0, arr.length - 1);
        }

        private void lensort(int arr[], int l, int r) {
            if (l < r) {
                int m = (l + r) / 2;
                lensort(arr, l, m);
                lensort(arr, m + 1, r);
                merge(arr, l, m, r);
            }
        }
    }
}