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.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Skier {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = Integer.parseInt(sc.nextLine());
        for (int i = 0; i < t; i++) {
            String str = sc.nextLine();
            //System.out.println(str);
            // int [][] passedPoints = new int[str.length()][3];
            // for (int[]arr:passedPoints)
            //   Arrays.fill(arr,Integer.MIN_VALUE);
            int numN= 0;
            int numS = 0;
            int numE = 0;
            int numW = 0;
            int x = 0;
            int y = 0;
            int maxX = 0;
            int minX = 0;
            int maxY = 0;
            int minY = 0;
            for (int j = 0; j < str.length(); j++) {
                if (str.charAt(j)=='N') {numN++;y++;}
                else if (str.charAt(j)=='S') {numS++;y--;}
                else if (str.charAt(j)=='E') {numE++;x++;}
                else {numW++; x--;}
                maxX = Math.max(maxX, x);
                maxY = Math.max(maxY, y);
                minX = Math.min(minX, x);
                minY = Math.min(minY, y);
            }
            boolean [][] xChart = new boolean[maxX - minX+1][maxY - minY+1];
            boolean [][] yChart = new boolean[maxX - minX+1][maxY - minY+1];
            int time = 0;
            x=Math.abs(minX);
            y=Math.abs(minY);
            for (int j = 0; j < str.length(); j++) {
                char current = str.charAt(j);
                int savedX = Integer.MAX_VALUE;
                int savedY = Integer.MAX_VALUE;
                int direction = 0;
                if (current =='N') {
                    direction = 1;
                    savedY = y;
                    y++;
                }
                else if (current=='S') {
                    direction = 1;
                    y--;
                    savedY = y;
                }
                else if (current=='W') {
                    direction = 2;
                    x--;
                    savedX = x;
                }
                else if (current=='E') {
                    direction = 2;
                    savedX = x;
                    x++;
                }
                boolean hasPassed = false;
                if (direction == 1) {
                    if  (yChart[x][savedY]) hasPassed = true;
                }
                else {
                    if (xChart[savedX][y]) hasPassed = true;
                }
                // System.out.println(Arrays.deepToString(passedPoints));
                //  System.out.println(savedX);
                //   System.out.println(savedY);
                if (hasPassed) time++;
                else time +=5;
                if (direction == 1) {
                    yChart[x][savedY] = true;
                }
                else {
                    xChart[savedX][y] = true;
                }
            }
            System.out.println(time);
        }
    }
}