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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Objects;
import java.util.Scanner;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author IncubatorMan
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        CSkier solver = new CSkier();
        int testCount = Integer.parseInt(in.next());
        for (int i = 1; i <= testCount; i++)
            solver.solve(i, in, out);
        out.close();
    }

    static class CSkier {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            String data;
            data = in.next();
            int len = data.length();
            HashSet<P> trak;
            trak = new HashSet<P>();
            Point nn = new Point(0, 0);
            int time = 0;
            for (int i = 0; i < len; i++) {
                char c = data.charAt(i);
                Point k = new Point(nn.x, nn.y);
                if (c == 'N') {
                    k.x++;
                } else if (c == 'S') {
                    k.x--;
                } else if (c == 'E') {
                    k.y++;
                } else {
                    k.y--;
                }

                P aa, bb;
                aa = new P(k, nn);
                bb = new P(nn, k);
                if (trak.contains(aa) || trak.contains(bb)) {
                    time++;
                    nn = new Point(k.x, k.y);
                    continue;
                }
                time += 5;
                trak.add(aa);
                trak.add(bb);

                //out.println(nn.x + " " + nn.y);
                //out.println(k.x + " " + k.y);

                nn = new Point(k.x, k.y);


            }
            //out.println(trak);
            out.println(time);
        }

        class Point {
            public int x;
            public int y;

            Point(int x, int y) {
                this.x = x;
                this.y = y;
            }

            public boolean equals(Object o) {
                if (this == o) return true;
                if (!(o instanceof Point)) return false;
                Point point = (Point) o;
                return x == point.x &&
                        y == point.y;
            }

            public int hashCode() {
                return Objects.hash(x, y);
            }

        }

        class P {
            public Point a;
            public Point b;

            P(Point a, Point b) {
                this.a = a;
                this.b = b;
            }

            public boolean equals(Object o) {
                if (this == o) return true;
                if (!(o instanceof P)) return false;
                P p = (P) o;
                return Objects.equals(a, p.a) &&
                        Objects.equals(b, p.b);
            }

            public int hashCode() {
                return Objects.hash(a, b);
            }

        }

    }
}

