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

public class cfpract2 {
    static int mod=10000_00007;
    static long oans=0,pw=0;
    static boolean fg=true;
   
    public static void solve() throws Exception{
        InputStreamReader ip=new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(ip);
        int t = Integer.parseInt(br.readLine());
        StringBuilder asb=new StringBuilder();

       while(t-->0){
        // int n =Integer.parseInt(br.readLine());
        // String[] strs=(br.readLine()).trim().split(" ");
        // int n=Integer.parseInt(strs[0]),l=Integer.parseInt(strs[1]),r=Integer.parseInt(strs[2]),s=Integer.parseInt(strs[3]);
         String str=(br.readLine()).trim();
        // int[] arr=new int[n];
        // for(int i=0;i<n;i++){arr[i]=Integer.parseInt(strs[i]);}
        int ctn=0,cts=0,cte=0,ctw=0;

        int n=str.length();
        for(int i=0;i<n;i++){
            char ch=str.charAt(i);
            if(ch=='N'){ ctn++; }
            else if(ch=='S'){cts++;}
            else if(ch=='E'){ cte++; }
            else if(ch=='W'){ctw++;}

        }

       
        
        HashSet<String> hs=new HashSet<>();  //option-1 using HashSet<String> hs as visited array
        long ans=0;                         //HashSet add,contains,remove take o(1)  time
        // boolean[][] arr=new boolean[ctn+cts+100][cte+cts+100];  
         // String[][] arr=new String[ctn+cts+100][ctw+cte+100]; //Give TLE 
        int i=ctn+50,j=ctw+50;
        for(int r=0;r<n;r++){
            char ch=str.charAt(r);
            int oi=i,oj=j;
            // if(arr[i][j]==null){arr[i][j]="";}
            // boolean fg=false;

            // for(char ch1:(arr[i][j]).toCharArray()){
            //     if(ch1==ch){fg=true;  break;}
            // }

            if(ch=='N'){  i--; }
            else if(ch=='S'){ i++;}
            else if(ch=='E'){ j++; }
            else if(ch=='W'){ j--;}

            // if(!fg){
            //     ans+=5;
            //     arr[oi][oj]+=ch;
            //     if(ch=='N' || ch=='S'){
            //         ch=ch=='N'?'S':'N';
            //     }else{
            //         ch=ch=='E'?'W':'E';
            //     }
            //     arr[i][j]+=ch; 
            // }else{
            //     ans+=1;
            // }
            String ps1=oi+""+oj+"$"+i+""+j;
            String ps2=i+""+j+"$"+oi+""+oj;
            if(hs.add(ps1) && hs.add(ps2)){
                ans+=5;
            }else{
                ans++;
            }
        }

        asb.append(ans);   asb.append("\n");
       }
       System.out.println(asb);
    }

       


    //******************************************************************************************************************** */
    public static void main(String[] args) throws Exception{
        // int[] arr={1,6,7};
        // ArrayList<int[]> list=new ArrayList<>();
        // list.add(new int[]{4,4});
        // // arr[1]-=3;
        // int[] arr1=list.get(0);   arr1[1]-=4;
        // arr1=list.get(0);
        // System.out.println(arr1[1]);

        solve();
        // sec();
     }

     public static void solve2() throws Exception{
        InputStreamReader ip=new InputStreamReader(System.in);
        BufferedReader br = new BufferedReader(ip);
        int t = Integer.parseInt(br.readLine());
        StringBuilder asb=new StringBuilder();

       while(t-->0){
        // int n =Integer.parseInt(br.readLine());
        // String[] strs=(br.readLine()).trim().split(" ");
        // int n=Integer.parseInt(strs[0]),l=Integer.parseInt(strs[1]),r=Integer.parseInt(strs[2]),s=Integer.parseInt(strs[3]);
        //  String str=(br.readLine()).trim();
        // int[] arr=new int[n];
        // for(int i=0;i<n;i++){arr[i]=Integer.parseInt(strs[i]);}

       }
    }

    
    //binexp
    public static long binexp(long a,long b){
        if(b==0)return 1;

        long res=binexp(a, b/2);

        if(b%2==1){
            return (((res*res))*a);    //%mod;
        }else return (res*res);
    }
    //gcd
    public static long gcd(long a,long b){   //gcd using division method
        if(b==0)return a;
        else return gcd(b, a%b);
    }


    public static int isprime(int n){
        for(int i=2;i<=Math.sqrt(n);i++){
            if(n%i==0)return i;
        }

        return -1;
    }


    //sort
     public static void sort(long[] arr) {
		int n = arr.length;
		for (int i = 0; i < n; i++) {
			int idx = (int) Math.random() * n;
			long temp = arr[i];  arr[i] = arr[idx];  arr[idx] = temp;  //swap
		}
		Arrays.sort(arr);
	}
 
	public static void sort(int[] arr) {
		int n = arr.length;
		for (int i = 0; i < n; i++) {
			int idx = (int) Math.random() * n;
			int temp = arr[i];  arr[i] = arr[idx]; arr[idx] = temp;  //swap
		}
		Arrays.sort(arr);
	}
    //1d print
    public static void print(int[] dp) {
		for (int val : dp) {
			System.out.print(val + " ");
		}
		System.out.println();
	}
 
	public static void print(long[] dp) {
		for (long val : dp) {
			System.out.print(val + " ");
		}
		System.out.println();
	}  
    //2d print
	public static void print(long[][] dp) {
		for (long[] a : dp) {
			for (long val : a) {
				System.out.print(val + " ");
			}
			System.out.println();
		}
	}
 
	public static void print(int[][] dp) {
		for (int[] a : dp) {
			for (int val : a) {
				System.out.print(val + " ");
			}
			System.out.println();
		}
	}
 
	
}



