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 Main {
 
	public static void main(String[] args) throws IOException,InterruptedException{
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		while(t-->0) {
			int c=0;
			char[] arr=sc.next().toCharArray(); 
			HashSet<String> hs=new HashSet();
			pair cur=new pair(0,0);
			for (int i = 0; i < arr.length; i++) {
//				pw.println(hs);
				if (arr[i]=='N') {
					if(hs.contains(cur.x+" "+cur.y+" "+cur.x+" "+(cur.y+1))||hs.contains(cur.x+" "+(cur.y+1)+" "+cur.x+" "+cur.y)) {
						c++;
					}else {
						c+=5;
						hs.add(cur.x+" "+cur.y+" "+cur.x+" "+(cur.y+1));
						hs.add(cur.x+" "+(cur.y+1)+" "+cur.x+" "+cur.y);
					}
					cur.y++;
				}else if (arr[i]=='S') {
					if(hs.contains(cur.x+" "+cur.y+" "+cur.x+" "+(cur.y-1))||hs.contains((cur.x+" "+(cur.y-1)+" "+cur.x+" "+cur.y))) {
						c++;
					}else {
						c+=5;
						hs.add(cur.x+" "+cur.y+" "+cur.x+" "+(cur.y-1));
						hs.add(cur.x+" "+(cur.y-1)+" "+cur.x+" "+cur.y);
					}
					cur.y--;
				}else if (arr[i]=='E') {
					if(hs.contains(cur.x+" "+cur.y+" "+(cur.x+1)+" "+cur.y)||hs.contains((cur.x+1)+" "+cur.y+" "+cur.x+" "+cur.y)) {
						c++;
					}else {
						c+=5;
						hs.add(cur.x+" "+cur.y+" "+(cur.x+1)+" "+cur.y);
						hs.add((cur.x+1)+" "+cur.y+" "+cur.x+" "+cur.y);
					}
					cur.x++;
				}else {
					if(hs.contains(cur.x+" "+cur.y+" "+(cur.x-1)+" "+cur.y)||hs.contains((cur.x-1)+" "+cur.y+" "+cur.x+" "+cur.y)) {
						c++;
					}else {
						c+=5;
						hs.add(cur.x+" "+cur.y+" "+(cur.x-1)+" "+cur.y);
						hs.add((cur.x-1)+" "+cur.y+" "+cur.x+" "+cur.y);
					}
					cur.x--;
				}
			}
			pw.println(c);
		}
		pw.close();
    }
	static HashSet<Long> primes;
	static PrintWriter pw=new PrintWriter(System.out);
	static long pow(int a,int b) {
		long r=1l;
		for (int i = 0; i < b; i++) {
			r*=a;
		}
		return r;
	}
	static void primes() {
		boolean[] freq=new boolean[1000000];
		for (int i = 0; i < freq.length; i++) {
			freq[i]=true;
		}
		primes=new HashSet<>();
		for (int i = 2; i <= 1e3; i++) {
			if(freq[i-1]) {
				for (int j = i*i; j <= 1e6; j+=i) {
					freq[j-1]=false;
				}
			}
		}
		for (int i = 2; i < freq.length; i++) {
			if(freq[i-1]) primes.add((long)(i));
		}
	}
	static long gcd(long x,long y) {
		while (x!=y) {
			if(Math.max(x,y)/Math.min(x,y)==(double)(Math.max(x,y))/Math.min(x,y)) return Math.min(x,y);
			if(primes.contains(x)) {
				if(y/x==y/(double)x) return x;
				else return 1;
			}else if (primes.contains(y)) {
				if(x/y==x/(double)y) return y;
				else return 1;
			}
			if(x>y) x-=y;
			else y-=x;
		}
		return x;
	}
	static class pair implements Comparable<pair> {
		int x;
		int y;
 
		public pair(int x, int y) {
			this.x = x;
			this.y = y;
		}
 
		public String toString() {
			return x + " " + y;
		}
		public boolean equals(Object o) {
            if (o instanceof pair) {
                pair p = (pair)o;
                return p.x == x && p.y == y;
            }
            return false;
        }
        public int hashCode() {
            return new Double(x).hashCode() * 31 + new Double(y).hashCode();
        }
        public int compareTo(pair other) {
        	if(this.x==other.x) {
        		return Long.compare(this.y, other.y);
        	}
			return Long.compare(this.x, other.x);
		}
	}
	static class tuble implements Comparable<tuble> {
		int x;
		int y;
		int z;
 
		public tuble(int x, int y, int z) {
			this.x = x;
			this.y = y;
			this.z = z;
		}
 
		public String toString() {
			return x + " " + y + " " + z;
		}
 
		public int compareTo(tuble other) {
			if (this.x == other.x) {
				return this.y - other.y;
			} else {
				return this.x - other.x;
			}
		}
	}
 	static class Scanner {
		StringTokenizer st;
		BufferedReader br;
 
		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}
 
		public boolean hasNext() {
			// TODO Auto-generated method stub
			return false;
		}
 
		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}
 
		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
 
		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}
 
		public String nextLine() throws IOException {
			return br.readLine();
		}
 
		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}
 
		public boolean ready() throws IOException {
			return br.ready();
		}
 
	}
 
}