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.io.BufferedReader;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;
import java.io.*; 
import javax.lang.model.util.ElementScanner6;
public class STRING{
    public static void main(String args[]) throws IOException{  
      BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));   
     PrintWriter writer = new PrintWriter(System.out);
     int t =Integer.parseInt(sc.readLine());
     
     while(t-->0){
        String s = sc.readLine();
        char [] arr = s.toCharArray();
        HashMap <String,Integer> map = new HashMap<>();
        String s1 ="",s2="",s3="";
        int x = 0 , y =0,sum=0;
        for(int i=0;i<arr.length;i++){ 
         s1=x+","+y;
          if(arr[i]=='N')
            y++;
         else if(arr[i]=='S')
            y--;
         else if(arr[i]=='E')
            x++;    
         else 
            x--;
         s2=x+","+y;
         s3=s2+"=>"+s1;
         s2 = s1+"=>"+s2;
        
         if(!( map.containsKey(s2) || map.containsKey(s3)))
           sum+=5;
         else
           sum+=1; 
          map.put(s2, i);  
        }
        
        writer.println(sum);
        writer.flush();

       }
     }
     
 }
  