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.lang.*;
import java.io.*;
import java.math.*;


 
public class Solution{
 
	public static Scanner scn = new Scanner(System.in);
	public static boolean multipleTC = true;
 
	public static void main (String[] args) throws java.lang.Exception{
		int T = multipleTC?scn.nextInt():1;
		while(T-- > 0) solve();
	}
 
	public static void solve(){
	    
        String str = scn.next();
        HashMap<Point, HashSet<Point>> map = new HashMap<>();
        Point prev = new Point(0,0);
        
        map.put(prev, new HashSet<>());
        
        int time = 0;
        
        for(char dir : str.toCharArray()){
        	
        	Point next = new Point(prev.x, prev.y);
        	
            switch(dir){
                case 'N' : next.y++; break;
                case 'S' : next.y--; break;
                case 'E' : next.x++; break;
                case 'W' : next.x--; break;
            }
            
            if(!map.containsKey(prev)) map.put(prev, new HashSet<>());
            if(!map.containsKey(next)) map.put(next, new HashSet<>());
            
            if(map.get(prev).contains(next) || map.get(next).contains(prev)){
                time += 1;
            } else {
                time += 5;
                map.get(prev).add(next);
            }
            
            prev = next;
        }
        
        pln(time);
	}
	
	public static void p(Object o){System.out.print(o + " ");}
	public static void pln(Object o){System.out.println("" + o);}
	public static void pln(){System.out.println("");}
}

class Point{

	int x;
	int y;
	
	public Point(){}

	public Point(int x, int y){
		this.x = x;
		this.y = y;
	}

	public int getX(){	return this.x;	}
	public void setX(int x){this.x = x;	}

	public int getY(){	return this.y;	}
	public void setY(int y){this.y = y; }

	public int distance(Point p2){
		double d = Math.pow(this.x - p2.x, 2) + Math.pow(this.y - p2.y, 2);
		return (int)Math.sqrt(d);
	}

	@Override
	public String toString() { 
		return String.format("(" + this.x + "," + this.y + ")"); 
	} 

	@Override
	public boolean equals(Object obj){
		if(this == obj || super.equals(obj)) return true;
		if(obj == null || !(obj instanceof Point)) return false;

		Point pt = (Point)obj;
		return pt.x == this.x && pt.y == this.y;
	}

	@Override
	public int hashCode(){
		return (int)((this.x * 19.0 + this.y * 29.0)%1000000007);
	}
}