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.util.Comparator;
import java.util.HashSet;
import java.util.Objects;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0){
            String s = sc.next();
            int prevx = 0, prevy = 0;
            int time = 0;
            HashSet<Edge> set = new HashSet<>();
            for(int i = 0; i < s.length(); i++){
                Pair start = new Pair(prevx, prevy);
                if(s.charAt(i) == 'N'){
                    prevy++;
                }else if(s.charAt(i) == 'S'){
                    prevy--;
                }else if(s.charAt(i) == 'E'){
                    prevx++;
                }else{
                    prevx--;
                }
                Pair end = new Pair(prevx, prevy);
                Edge edge = new Edge(start, end);
                Edge reverse = new Edge(end, start);
                if(set.contains(edge) || set.contains(reverse)){
                    time++;
                }else{
                    set.add(edge);
                    time += 5;
                }
            }
            System.out.println(time);
        }
    }

    static class Edge{
        Pair start, end;
        public Edge(Pair start, Pair end){
            this.start = start;
            this.end = end;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Edge edge = (Edge) o;
            return (edge.start.key == start.key && edge.start.value == start.value && edge.end.key == end.key && edge.end.value == end.value);
        }

        @Override
        public int hashCode() {

            return Objects.hash(start.key+" "+start.value+" "+end.key+ " "+end.value);
        }
    }

    static class Pair{
        int key,value;
        public Pair(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
}
