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

public class Factors {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
            int t = sc.nextInt();
            while(t-->0){
                String s;
                s = sc.next();
                char sArr[] = s.toCharArray();

                HashSet<Segment> segments = new HashSet<>();

                int currX = 0, currY = 0;
                int ans = 0;

                for (int j = 0; j < sArr.length; j++) {
                    int newX = currX, newY = currY;
                    if (sArr[j] == 'N') {
                        newY++;
                    } else if (sArr[j] == 'S') {
                        newY--;
                    } else if (sArr[j] == 'E') {
                        newX++;
                    } else if (sArr[j] == 'W') {
                        newX--;
                    }

                    if (segments.contains(new Segment(currX, currY, newX, newY)) ||
                            segments.contains(new Segment(newX, newY, currX, currY))) {
                        ans += 1;
                    } else {
                        ans += 5;
                        segments.add(new Segment(currX, currY, newX, newY));
                    }

                    currX = newX;
                    currY = newY;
                }

                System.out.println(ans);
            }


    }

    static class Segment {
        int x1, y1;
        int x2, y2;

        public Segment(int x1, int y1, int x2, int y2) {
            this.x1 = x1;
            this.y1 = y1;
            this.x2 = x2;
            this.y2 = y2;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Segment segment = (Segment) o;
            return x1 == segment.x1 &&
                    y1 == segment.y1 &&
                    x2 == segment.x2 &&
                    y2 == segment.y2;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x1, y1, x2, y2);
        }
    }
}

