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 Main{
         public static void main(String[] args) throws IOException{
             BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             int itr = Integer.parseInt(br.readLine());
             while(itr-->0){
                     String s = br.readLine();
                     HashSet<String> hset = new HashSet<String>();
                   
                     int ans = 0 , x =0, y=0;
                     for(int i = 0 ;i<s.length();i++){
                         int X= 0,Y=0;
                         if(s.charAt(i)=='N'){
                            Y=1;
                             
                             
                         }else if(s.charAt(i)=='S'){
                              Y=-1;
                            
                         }else if(s.charAt(i)=='W'){
                             X =-1;
                            
                             
                         }else if(s.charAt(i)=='E'){
                             
                             X =1;
                            
                         }
                         X = x+X;
                         Y = y+Y;
                         
                         String seg1 = x+" "+y+" "+X+" "+Y;
                         String seg2 = X+" "+Y+" "+x+" "+y;
                      //   System.out.println(seg1+" "+seg2);
                         if(hset.contains(seg1) || hset.contains(seg2))
                           ans+=1;
                          else 
                           ans +=5;
                          
                          hset.add(seg1);
                          hset.add(seg2);
                          x = X;
                          y = Y;
                         
                         
                         
                     }
                     
                     System.out.println(ans);
                     
             }
         }
}