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

public class Main {
    private static final boolean ONLINE_JUDGE = System.getProperty("ONLINE_JUDGE") != null;

    void Solve() throws IOException {
        int t = readInt();
        while (t-- > 0) {
            var arr = readString().toCharArray();
            var horizontal = new TreeSet<>((Comparator<Pair<Integer, Integer>>) (a, b) -> {
                if (!Objects.equals(a.getKey(), b.getKey())) {
                    return Integer.compare(a.getKey(), b.getKey());
                } else {
                    return Integer.compare(a.getValue(), b.getValue());
                }
            });
            var vertical = new TreeSet<>((Comparator<Pair<Integer, Integer>>) (a, b) -> {
                if (!Objects.equals(a.getKey(), b.getKey())) {
                    return Integer.compare(a.getKey(), b.getKey());
                } else {
                    return Integer.compare(a.getValue(), b.getValue());
                }
            });
            int ans = 0;
            int x = 0;
            int y = 0;

            for (char c : arr) {
                int dx = c == 'N' ? 1 : c == 'S' ? -1 : 0;
                int dy = c == 'W' ? 1 : c == 'E' ? -1 : 0;
                var pt = new Pair<>(Math.min(x, x + dx), Math.min(y, y + dy));
                ans++;
                if (dx != 0 && !horizontal.contains(pt)) {
                    ans += 4;
                    horizontal.add(pt);
                } else if (dy != 0 && !vertical.contains(pt)) {
                    ans += 4;
                    vertical.add(pt);
                }
                x += dx;
                y += dy;
            }

            out.print(ans + "\n");
        }
    }

    public static void main(String[] args) {
        new Main();
    }

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok;

    Main() {
        try {
            long timeStart = System.currentTimeMillis();
            if (ONLINE_JUDGE) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader("input.txt"));
                out = new PrintWriter("output.txt");
            }
            tok = new StringTokenizer("");
            Solve();
            out.close();
            long timeEnd = System.currentTimeMillis();
            System.err.println("time = " + (timeEnd - timeStart) + " compiled");
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(-1);
        }
    }

    String readLine() throws IOException {
        return in.readLine();
    }

    String delimiter = " ";

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            String nextLine = readLine();
            if (nextLine == null)
                return null;
            tok = new StringTokenizer(nextLine);
        }
        return tok.nextToken(delimiter);
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    int[] sortArrayInt(int[] a) {
        Integer[] arr = new Integer[a.length];
        for (int i = 0; i < a.length; i++) {
            arr[i] = a[i];
        }
        Arrays.sort(arr);
        for (int i = 0; i < a.length; i++) {
            a[i] = arr[i];
        }
        return a;
    }

    void sortArrayLong(long[] a) {
        Long[] arr = new Long[a.length];
        for (int i = 0; i < a.length; i++) {
            arr[i] = a[i];
        }
        Arrays.sort(arr);
        for (int i = 0; i < a.length; i++) {
            a[i] = arr[i];
        }
    }
}