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
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;



/* Name of the class has to be "Main" only if the class is public. */
public class Main
 
 
{
    static Scanner in = new Scanner(System.in);
    
    public static void solve()
    {
        //in.nextLine();
        
        String s=in.nextLine();
        
     //System.out.println(s);
        
        HashSet<List<Long>> map = new HashSet<>();
        
        long x=0,y=0;
        //List<Long> ad= new ArrayList<>();
        
       
        
        int cost=0;
        for(int i=0;i<s.length();i++)
        {
              List<Long> ads= new ArrayList<>();
            ads.add(x);
            ads.add(y);
            if(s.charAt(i)=='N')
            y++;
            else if(s.charAt(i)=='S')
            y--;
            else if(s.charAt(i)=='W')
            x--;
            else
            x++;
            
            ads.add(x);
            ads.add(y);
            
            List<Long> ads2= new ArrayList<>();
            ads2.add(ads.get(2));
            ads2.add(ads.get(3));
            ads2.add(ads.get(0));
            ads2.add(ads.get(1));
            
            //System.out.println(s.charAt(i)+" "+x+" "+y);
            
           if(!map.contains(ads) && !map.contains(ads2))
           {
               cost+=5;
               map.add(ads);
              
           }
           else
           {
               cost++;
           }
     
            
            
        }
        
        
        System.out.println(cost);
        
       
        
    }
    

    
	public static void main (String[] args) throws java.lang.Exception
	{
		// your code goes here
		
		int t=in.nextInt();
		in.nextLine();
		
		while(t>0)
		{
		    
		    solve();
		    t--;
		}
		
		
	
	//	System.out.println(x);
	}
}
