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.HashSet;
import java.util.Scanner;
import java.util.Set;

/**
 *
 * @author MasterEx
 */
public class P1351C {
    
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        for (int i=0; i<t; i++) {
            String route = in.next();
            Set<String> existingRoutes = new HashSet<>();
            int north = 0;
            int east = 0;
            int time = 0;
            for (int j=0; j<route.length(); j++) {
                char c = route.charAt(j);
                char dir = 'N';
                if (c == 'N') {
                    north++;
                } else if (c == 'E') {
                    east++;
                    dir = 'E';
                } else if (c == 'W') {
                    east--;
                    dir = 'E';
                } else if (c == 'S') {
                    north--;
                    dir = 'N';
                }
                String pos = "" + north + "N" + east + "E" + dir;
                if (c == 'S') {
                    pos = "" + (north+1) + "N" + east + "E" + dir;
                } else if (c == 'W') {
                    pos = "" + north + "N" + (east+1) + "E" + dir;
                }
                if (existingRoutes.contains(pos)) {
                    time++;
                } else {
                    time += 5;
                }
                existingRoutes.add(pos);
            }
            System.out.println(time);
        }
    }
    
}
