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

public class Main {
    static byte[][] dir = {
            {1, 2},
            {2, 1},
            {4, 8},
            {8, 4},

    };
    public static void main(final String[] args) {
        final Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        while (num-- != 0) {
            final String s = in.next();
            // byte[][] map = new byte[2*s.length() + 2][2*s.length() + 2];
            // Map<P, Boolean> map = new Map<P, Boolean>(100000);
            TreeSet<P> tree_set = new TreeSet<P>();
            int n = s.length();
            int i = 0;
            int j = 0;
            int i_p = 0;
            int j_p = 0;
            int ans = 0;
            for (int k = 0; k < s.length(); k++) {
                i_p = i;
                j_p = j;
                char tmp = s.charAt(k);
                int d = 0;
                switch (tmp) {
                    case 'N': //1
                        i++;
                        d=0;
                        break;
                    case 'S'://2
                        i--;
                        d=1;
                        break;
                    case 'E'://4
                        j++;
                        d=2;
                        break;
                    case 'W'://8
                        d=3;
                        j--;
                        break;
                }
                if (tree_set.contains(new P(i_p, j_p, i, j))) {
                    ans += 1;
                } else {
                    ans += 5;
                    tree_set.add(new P(i_p, j_p, i, j));
                    tree_set.add(new P(i, j, i_p, j_p));
//                    map[i_p + n][j_p + n] |= dir[d][0];
//                    map[i + n][j + n] |= dir[d][1];
                }
            }
            System.out.println (ans);
        }
    }

}
class P implements Comparable<P> {
    int x;
    int y;
    int x_p;
    int y_p;
    P (int a, int b, int c, int d) {
        x = c;
        y = d;
        x_p = a;
        y_p = b;
    }


    @Override
    public int compareTo(P o) {
        if (x_p != o.x_p) return x_p - o.x_p;
        else if (y_p != o.y_p) return y_p - o.y_p;
        else if (x != o.x) return x - o.x;
        else return y - o.y;
    }
}