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 Solution {
    private static int solve(char[] moves) {
        Set<List<Integer>> used = new HashSet<>();

        int x = 0;
        int y = 0;

        int result = 0;
        for (char c : moves) {

//            System.out.println(used);
//            System.out.printf("x: %d, y: %d, move: %s\n", x, y, c);
            List<Integer> edge = new LinkedList<>();
            edge.add(x);
            edge.add(y);
            edge.add((int)c);
            boolean fresh = !used.contains(edge);
            if (!fresh) result += 1;
            else {
                result += 5;
                used.add(edge);
            }

            if (c == 'N') y += 1;
            else if (c == 'S') y -= 1;
            else if (c == 'W') x -= 1;
            else x += 1;

            if (fresh) {
                char d = 'S';
                if (c == 'S') d = 'N';
                else if (c == 'W') d = 'E';
                else if (c == 'E') d = 'W';

                edge = new LinkedList<>();
                edge.add(x);
                edge.add(y);
                edge.add((int)d);
                used.add(edge);
            }
        }

        return result;
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int T = in.nextInt();
        in.nextLine();

        for (int t = 0; t < T; t += 1) {
            char[] moves = in.nextLine().trim().toCharArray();

            System.out.println(solve(moves));
        }
    }
}
