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



public class Solution {
    FastIO io = new FastIO();
    int t;
    String path;
    Set<String> st;

    String hash(int[] ps){
        StringBuilder sb1 = new StringBuilder();
        StringBuilder sb2 = new StringBuilder();
        sb1.append(ps[0]); sb1.append(ps[1]);
        sb2.append(ps[2]); sb2.append(ps[3]);
        String s1 = sb1.toString(), s2 = sb2.toString();
        if(s1.compareTo(s2) > 0){
            String t = new String(s1);
            s1 = s2; s2 = t;
        }
        StringBuilder sb = new StringBuilder();
        sb.append(s1); sb.append(s2);
        return sb.toString();
    }

    long solve() {
        st = new HashSet<>();
        int x=0, y=0;
        long res = 0;
        for(int i=0; i<path.length(); i++){
            char c = path.charAt(i);
            int x1 = x, y1 = y;
            if(c == 'S'){
                y1--;
            }else if(c == 'N'){
                y1++;
            }else if(c == 'E'){
                x1++;
            }else{
                x1--;
            }

            int[] p = new int[]{x,y,x1,y1};
            String hp = hash(p);
            if(st.contains(hp)){
                res += 1;
            }else{
                res += 5;
            }
            st.add(hp);
            x = x1; y = y1;
        }

        return res;
    }

    public Solution() throws Exception {
        t = io.nextInt();
        while(t-- > 0){
            path = io.next();
            io.write(solve(), "\n");
        }
        io.flush();
    }

    public static void main(String[] args) throws Exception {
        //System.setIn(new FileInputStream("input.txt"));
        Solution s = new Solution();
    }
}

class FastIO {
    BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter output = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer sk;
    public int nextInt() throws Exception {
        return Integer.parseInt(next());
    }

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

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

    public double nextFloat() throws Exception {
        return Float.parseFloat(next());
    }

    public String next() throws Exception {
        if(sk != null && sk.hasMoreElements()){
            return sk.nextToken();
        }

        String line = null;
        while(line == null || line.isEmpty()){
            line = input.readLine();
        }
        sk = new StringTokenizer(line);
        return sk.nextToken();
    }

    public void write(int v, String sep) throws Exception {
        output.write(Integer.toString(v));
        if(sep != null && !sep.isEmpty()){
            output.write(sep);
        }
    }

    public void write(long v, String sep) throws Exception {
        output.write(Long.toString(v));
        if(sep != null && !sep.isEmpty()){
            output.write(sep);
        }
    }

    public void write(double v, String sep) throws Exception {
        output.write(Double.toString(v));
        if(sep != null && !sep.isEmpty()){
            output.write(sep);
        }
    }

    public void write(float v, String sep) throws Exception {
        output.write(Float.toString(v));
        if(sep != null && !sep.isEmpty()){
            output.write(sep);
        }
    }

    public void write(String s, String sep) throws Exception {
        output.write(s);
        if(sep != null && !sep.isEmpty()){
            output.write(sep);
        }
    }

    public void flush() throws Exception {
        output.flush();
    }
}
