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.*;
public class MyClass {
static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
    
    static long solve(long n)
    {
        if(n<=4)
        {
            return Math.max(n-1,1);
        }
        if(n%4==0 || n%2==1)
        return (n-solve(n-1));
        return (n-solve(n/2));
    }
    public static void main(String args[]) 
{
	FastReader s=new FastReader();int t=0;int n=0,ans=0,i=0,j=0,count=0,x1=0,y1=0;String str="";
     //Scanner in=new Scanner(System.in);
     //if(in.hasNext())
     t=s.nextInt();
     for(int j1=0;j1<t;j1++)
     {
      //   if(in.hasNext())
         str=s.next();
         i=0;j=0;
         ArrayList<Integer> al=new ArrayList<>();
         al.add(i);
         al.add(j);
         al.add(i);
         al.add(j);
         HashSet<ArrayList<Integer>> set=new HashSet<>();
         set.add(al);
         count=0;
         for(int i1=0;i1<str.length();i1++)
         {
             x1=i;
             y1=j;
             char ch=str.charAt(i1);
             if(ch=='N')
             {
                 j++;
             }
             else if(ch=='W')
             i--;
             else if(ch=='S')
             j--;
             else
             i++;
             ArrayList<Integer> al2=new ArrayList<>();
            al2.add(i);
            al2.add(j);
            al2.add(x1);
            al2.add(y1);
            
              ArrayList<Integer> al3=new ArrayList<>();
            al3.add(x1);
            al3.add(y1);
            al3.add(i);
            al3.add(j);
            
            //System.out.println("i="+i+" j="+j);
            //System.out.println(set);
            if(set.contains(al2) || set.contains(al3))
            {count+=1;}
            else
            {count+=5; set.add(al2);}
           
         }
         System.out.println(count);
         
     }
    }
}