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.*;

public class JavaApplication161 {

    /**
     * @param args the command line arguments
     */
    static class node{
        int x;
        int y;
        public node(int x, int y)
        {
            this.x=x;
            this.y=y;
        }
    }
    public static void main(String[] args) {
        // TODO code application logic here
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
       while(t--!=0)
       {
         String s=sc.next();
         int n=s.length();
         HashSet<Integer >x=new HashSet<>();
          HashSet<Integer >y=new HashSet<>();
          HashSet<String> no=new HashSet<>();
          int x1=0;
          int y1=0;
          int pre_x=0;
          int pre_y=0;
          String s1="0 0 0 0";
          String s2="";
          long sum=0;
          no.add(s1);
         for(int i=0;i<n;i++)
         {
             
             if(s.charAt(i)=='N')
             {
                 y1++;
             }
             else if(s.charAt(i)=='S')
             {
                 y1--;
             }
              else if(s.charAt(i)=='E')
             {
                 x1++;
             }
              else if(s.charAt(i)=='W')
             {
                 x1--;
             }
             s1=pre_x+" "+pre_y+" "+x1+" "+y1;
             s2=x1+" "+y1+" "+pre_x+" "+pre_y;
            // System.out.println(s1);
             
             pre_x=x1;
             pre_y=y1;
             if(no.contains(s1) ||no.contains(s2))
             {
                 sum=sum+1;
             }
             else
             {
                 sum=sum+5;
                 no.add(s1);
                        
             }
                     
             
             
             
         }
         System.out.println(sum);

       }
                
    }
    
}
