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 javafx.util.Pair; 
public class Main
{
    
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int t = s.nextInt();
		
		String[] strarr = new String[t+1];
		for(int i = 0; i <= t; i++)
		    strarr[i] = s.nextLine();
		 
		 for(int i = 1; i <= t; i++){
		    
		    int px = 0, py = 0, x = 0, y = 0;
		    Set<Pair<Integer, Integer>> set = new HashSet();
		    int ans = 0;
		    for(char cc : strarr[i].toCharArray()){
		        px = x; py = y;
		        
		        switch(cc){
		            case 'N':
		                y++; break;
		            case 'S':
		                y--; break;
		            case 'W':
		                x--; break;
		            case 'E':
		                x++; break;
		        }
		        
		        Pair<Integer, Integer> curp = new Pair<>(px + x,py + y);
		        if(set.contains(curp)) ans+=1;
		        else{
		            ans+=5;
		            set.add(curp);
		        }
		        
		        
		    }
		    System.out.println(ans);
		 }

	}
}
