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.*;
import java.lang.*;

public class Solution{


    public static String format(Integer arr1[] , Integer arr2[]){
        String ans = "";
        ans += arr1[0];
        ans += arr1[1];
        ans += arr2[0];
        ans += arr2[1];
        
        return ans;
    }




    public static long solve(String str){
        int time = 0;
        HashSet<String> set = new HashSet<>();
        Integer[] arr = new Integer[2];
        Integer[] prev = new Integer[2];
        for(int i = 0 ; i < arr.length ; i++){
            arr[i] = 0;
        }
        
        for(char ch : str.toCharArray()){
            if(ch == 'N'){
                prev[0] = arr[0];
                prev[1] = arr[1];
                arr[0] = 1 + arr[0];
                String st = format(arr , prev);
                String sr = format(prev , arr);
                // System.out.println(format(arr));
                if(set.contains(st)){
                    time += 1;
                }else{
                    time += 5;
                    set.add(st);
                    set.add(sr);
                }
            }else if(ch == 'S'){
                prev[0] = arr[0];
                prev[1] = arr[1];
                arr[0] = -1 + arr[0];
                String st = format(arr , prev);
                String sr = format(prev , arr);
                // System.out.println(format(arr));
                if(set.contains(st)){
                    time += 1;
                }else{
                    time += 5;
                    set.add(st);
                    set.add(sr);
                }
            }else if(ch == 'W'){
                prev[0] = arr[0];
                prev[1] = arr[1];
                arr[1] = 1 + arr[1];
                String st = format(arr , prev);
                String sr = format(prev , arr);
                // System.out.println(format(arr));
                if(set.contains(st)){
                    time += 1;
                }else{
                    time += 5;
                    set.add(st);
                    set.add(sr);
                }
            }else if(ch == 'E'){
                prev[0] = arr[0];
                prev[1] = arr[1];
                arr[1] = -1 + arr[1];
                String st = format(arr , prev);
                String sr = format(prev , arr);
                // System.out.println(format(arr));
                if(set.contains(st)){
                    time += 1;
                }else{
                    time += 5;
                    set.add(st);
                    set.add(sr);
                }
            }
        }

        return time;
    }

    public static void gora(){
        Scanner scn = new Scanner(System.in);

        // long test = scn.nextLong();

        long n = scn.nextLong();

        // long arr[] = new long[n];
        scn.nextLine();
        for(int i = 0 ; i < n ; i++){
 
            String str = scn.nextLine();
            System.out.println(solve(str));
        }

        
    }

    public static void main(String args[]){
        gora();
    }
}