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
/**
 * ******* Created  on 7/5/20 7:36 PM*******
 */

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

public class del implements Runnable {

    private static final int MAX = (int) (1E5 + 5);
    private static final int MOD = (int) (1E9 + 7);
    private static final long Inf = (long) (1E14 + 10);
    private static final double eps = (double) (1E-9);
    class Pair{
        int a;
        int b;
        int c ;
        int d;
        Pair(int a , int b, int c,int d){
            this.a = a;
            this.b =b;
            this.c= c;
            this.d = d;
        }

        @Override
        public boolean equals(Object obj) {

            if(obj == null ||  obj.getClass() != this.getClass())
                return false;
            Pair o = (Pair) obj;
            if(o.a == this.a  && o.b == this.b && o.c == this.c && o.d == this.d)
                return true;
            return false;
        }

        @Override
        public int hashCode() {
            int hash =7;
            return this.a * hash + this.b;
        }
    }
    private void solve() throws IOException {
        int t = 1;
        t = reader.nextInt();
        Set<Pair> set = new HashSet<>();
        while (t-- > 0) {
            String s = reader.next();
            int n =  s.length();
            long res =0;
            set.clear();

            //set.add(new Pair(0,0));

            int prx =0, pry=0;
            for(int i=0;i<n;i++){
                int px = prx, py =pry;
                if(s.charAt(i)=='N')pry+=1;
                if(s.charAt(i)=='S')pry-=1;
                if(s.charAt(i)=='E')prx+=1;
                if(s.charAt(i)=='W')prx-=1;

                if(set.contains(new Pair(Math.min(prx, px),Math.min(pry,py), Math.max(prx,px),
                        Math.max(py,pry) )) )
                    res+=1L;
                else
                    res+=5L;
                set.add(new Pair(Math.min(prx, px),Math.min(pry,py), Math.max(prx,px),
                        Math.max(py,pry)));
            }
            writer.println(res);
        }
    }

    public static void main(String[] args) throws IOException {
        try (Input reader = new StandardInput(); PrintWriter writer = new PrintWriter(System.out)) {
            new del().run();
        }
    }

    StandardInput reader;
    PrintWriter writer;

    @Override
    public void run() {
        try {
            reader = new StandardInput();
            writer = new PrintWriter(System.out);
            solve();
            reader.close();
            writer.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }


    interface Input extends Closeable {
        String next() throws IOException;

        String nextLine() throws IOException;

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

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

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

        default int[] readIntArray() throws IOException {
            return readIntArray(nextInt());
        }

        default int[] readIntArray(int size) throws IOException {
            int[] array = new int[size];
            for (int i = 0; i < array.length; i++) {
                array[i] = nextInt();
            }
            return array;
        }

        default long[] readLongArray(int size) throws IOException {
            long[] array = new long[size];
            for (int i = 0; i < array.length; i++) {
                array[i] = nextLong();
            }
            return array;
        }
    }

    private static class StandardInput implements Input {
        private final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

        private StringTokenizer stringTokenizer;

        @Override
        public void close() throws IOException {
            reader.close();
        }

        @Override
        public String next() throws IOException {
            if (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                stringTokenizer = new StringTokenizer(reader.readLine());
            }
            return stringTokenizer.nextToken();
        }

        @Override
        public String nextLine() throws IOException {
            return reader.readLine();
        }
    }

}
