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 PA {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = Integer.valueOf(sc.nextLine());
        for(int i = 0; i<t; i++) {
            int result = 0;
            int currX = 0;
            int currY = 0;
            String path = sc.nextLine();
            HashMap<String, List<String>> map = new HashMap<>();
            for(int j = 0; j<path.length(); j++) {
                Character step = path.charAt(j);
                int newX = getNewXCoordinate(step,currX);
                int newY = getNewYCoordinate(step,currY);
                String newCoordinateString = newX + String.valueOf(newY);
                String oldCoordinateString = currX + String.valueOf(currY);
                if(map.containsKey(oldCoordinateString) && map.get(oldCoordinateString).stream().anyMatch(dest -> dest.equals(newCoordinateString))) result+=1;
                else if(map.containsKey(newCoordinateString) && map.get(newCoordinateString).stream().anyMatch(dest -> dest.equals(oldCoordinateString))) result+=1;
                else {
                    result += 5;
                    if(map.containsKey(oldCoordinateString)) {
                        map.get(oldCoordinateString).add(newCoordinateString);
                    } else {
                        map.put(oldCoordinateString, new ArrayList<>(Arrays.asList(newCoordinateString)));
                    }
                }
                currX = newX;
                currY = newY;
            }
            System.out.println(result);
        }
    }

    private static int getNewYCoordinate(Character step, int currY) {
        if(step.equals('E')) return currY+1;
        else if(step.equals('W')) return currY-1;
        else return currY;
    }

    private static int getNewXCoordinate(Character step, int currX) {
        if(step.equals('N')) return currX+1;
        else if(step.equals('S')) return currX-1;
        else return currX;
    }
}
