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 App {
    static class Node {
        boolean east, west, north, south;
    }

    public static void main( String[] args ) {
        Scanner sc = new Scanner(System.in);
        int testCaseCount = sc.nextInt();
        for (int t = 0; t < testCaseCount; t++) {
            determineTimeToRoll(sc.next());
        }
        sc.close();
    }

    static void determineTimeToRoll(String pathMapStr) {
        Map<String, Node> posNodeMap = new HashMap<>();
        Node currentPosition = new Node();
        int time = 0;
        int x = 100001, y = 10001;
        posNodeMap.put( x + "" + y, currentPosition);

        for (int i = 0; i < pathMapStr.length(); i++) {
            Node previousPosition = currentPosition;
            char direction = pathMapStr.charAt(i);
            if (direction == 'N') {
                y += 1;
                String key = x + "" + y;
                currentPosition = posNodeMap.get(key);

                if (currentPosition == null) {
                    currentPosition = new Node();
                }
                if (currentPosition.south) time += 1;
                else time += 5;
                previousPosition.north = true;
                currentPosition.south = true;
                posNodeMap.put(key, currentPosition);
            }
            else if (direction == 'S') {
                y -= 1;
                String key = x + "" + y;
                currentPosition = posNodeMap.get(key);

                if (currentPosition == null) {
                    currentPosition = new Node();
                }
                if (currentPosition.north) time += 1;
                else time += 5;
                previousPosition.south = true;
                currentPosition.north = true;
                posNodeMap.put(key, currentPosition);
            }
            else if (direction == 'E') {
                x += 1;
                String key = x + "" + y;
                currentPosition = posNodeMap.get(key);

                if (currentPosition == null) {
                    currentPosition = new Node();
                }
                if (currentPosition.west) time += 1;
                else time += 5;
                previousPosition.east = true;
                currentPosition.west = true;
                posNodeMap.put(key, currentPosition);
            }
            else {
                x -= 1;
                String key = x + "" + y;
                currentPosition = posNodeMap.get(key);

                if (currentPosition == null) {
                    currentPosition = new Node();
                }
                if (currentPosition.east) time += 1;
                else time += 5;
                previousPosition.west = true;
                currentPosition.east = true;
                posNodeMap.put(key, currentPosition);
            }
        }

        System.out.println(time);
    }
}
