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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Objects;
import java.util.Random;
import java.util.StringTokenizer;

public class Solution{
	
	static int[] dx = new int[] {0,+1,0,-1};
	static int[] dy = new int[] {-1,0,+1,0};
	static char[] opp =new char[] {'S','W','N','E'};
	static HashMap<Character, Integer> map;
	
	
	public static void main(String[] args) throws Exception{

		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		
		map = new HashMap<Character, Integer>();
		map.put('N',0);
		map.put('E', 1);
		map.put('S', 2);
		map.put('W', 3);
		
		
		int tt = fs.nextInt();
		while(tt-->0) {
			
			char[] arr = fs.next().toCharArray();
			int n = arr.length;
			
			HashSet<Path> set = new HashSet<Path>();
			
			int x = 0;
			int y = 0;
			int ans = 0;
			for(int i=0;i<n;i++) {
				if(set.contains(new Path(x,y,arr[i]))) {
					ans += 1;
				}
				else {
					ans += 5;
					set.add(new Path(x,y,arr[i]));
				}
				x += dx[map.get(arr[i])];
				y += dy[map.get(arr[i])];
			}
			
			out.println(ans);
			
		}
		
		out.close();
	}
	
	static class Path{
		int x;
		int y;
		char d;
		Path(int x , int y, char d){
			this.x = x;
			this.y = y;
			this.d = d;
		}
		
		@Override
		public boolean equals(Object o) {
			Path p = (Path)o;
			if(this.x == p.x && this.y == p.y && this.d == p.d) return true;
			if(this.x == (p.x + dx[map.get(p.d)]) && this.y == (p.y + dy[map.get(p.d)]) && this.d == opp[map.get(p.d)]) return true;
			return false;
		}
		
		@Override
		public int hashCode() {
			Path p = normalize(this);
			return Objects.hash(p.x, p.y, p.d);
		}
	}
	
	static Path normalize(Path o) {
		Path p = new Path(o.x,o.y,o.d);
		if(p.d=='S' || p.d=='E') {
			p.x += dx[map.get(p.d)];
			p.y += dy[map.get(p.d)];
			p.d = opp[map.get(p.d)];
		}
		return p;
	}
	
	
	
	
	
	
	
	static final Random random=new Random();
	
	static void ruffleSort(int[] a) {
		int n=a.length;//shuffle, then sort 
		for (int i=0; i<n; i++) {
			int oi=random.nextInt(n), temp=a[oi];
			a[oi]=a[i]; a[i]=temp;
		}
		Arrays.sort(a);
	}
	
	
	static class FastScanner{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer("");

		public String next(){
			while(!st.hasMoreElements()){
				try{
					st = new StringTokenizer(br.readLine());
				} catch(IOException e){
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		
		public String nextLine() throws IOException {
			return br.readLine();
		}
		
		public int nextInt(){
			return Integer.parseInt(next());
		}

		public int[] readArray(int n){
			int[] a = new int[n];
			for(int i=0;i<n;i++)
				a[i] = nextInt();
			return a;
		}
		
		public long nextLong() {
			return Long.parseLong(next());
		}
	}
	
}
