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.DataInputStream;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.HashSet;
import java.util.TreeSet;

public class C {
	static void merge(long arr[], int l, int m, int r) 
    { 
        int n1 = m - l + 1; 
        int n2 = r - m; 

        long L[] = new long [n1]; 
        long R[] = new long [n2]; 
        for (int i=0; i<n1; ++i) 
            L[i] = arr[l + i]; 
        for (int j=0; j<n2; ++j) 
            R[j] = arr[m + 1+ j]; 
        int i = 0, j = 0; 
        int k = l; 
        while (i < n1 && j < n2) 
        { 
            if (L[i] <= R[j]) 
            { 
                arr[k] = L[i]; 
                i++; 
            } 
            else
            { 
                arr[k] = R[j]; 
                j++; 
            } 
            k++; 
        } 
        while (i < n1) 
        { 
            arr[k] = L[i]; 
            i++; 
            k++; 
        } 
        while (j < n2) 
        { 
            arr[k] = R[j]; 
            j++; 
            k++; 
        } 
    } 
    static void sort(long arr[], int l, int r) 
    { 
        if (l < r) 
        { 
            int m = (l+r)/2; 
            sort(arr, l, m); 
            sort(arr , m+1, r); 
            merge(arr, l, m, r); 
        } 
    }
	//static PrintWriter out = new PrintWriter(System.out);
	public static void main(String[] args) throws IOException {
		try {
		BufferInput in = new BufferInput();
		StringBuilder sb = new StringBuilder();
		int t = in.nextInt();
		while(t-->0) {
			String s = in.nextString();
			HashMap<Pair, HashSet<Pair>> map = new HashMap<>();
			long ans = 0;
			int x=0;
			int y=0;;
			for(int i=0;i<s.length();i++) {
				int prevx = x;
				int prevy = y;
				if(s.charAt(i)=='N') {
					y++;
				}
				else if(s.charAt(i)=='S') {
					y--;
				}
				else if(s.charAt(i)=='W') {
					x--;
				}
				else if(s.charAt(i)=='E') {
					x++;
				}
				int f=0;
				Pair a = new Pair(prevx, prevy);
				Pair b = new Pair(x, y);
				if(map.containsKey(a)) {
					HashSet<Pair> set = map.get(a);
					if(set.contains(b)) {
						f=1;
						ans++;
					}
				}
				if(f==0&&map.containsKey(b)) {
					HashSet<Pair>set = map.get(b);
					if(set.contains(a)) {
						f=1;
						ans++;
					}
				}
				if(f==0){
					if(map.containsKey(a)) {
						HashSet<Pair> set = map.get(a);
						set.add(b);
						map.put(a, set);
					}
					else if(map.containsKey(b)) {
						HashSet<Pair> set = map.get(b);
						set.add(a);
						map.put(b, set);
					}
					else {
					HashSet<Pair> set = new HashSet<>();
					set.add(b);
					map.put(a, set);
					}
					ans+=5;
					
				}
			}
			sb.append(ans).append("\n");
			
		}
		System.out.print(sb);
	
		
}catch(Exception e) {}
	
}
//	static class Pair implements Comparable<Pair>
//	{
//	    int x;
//	    int y;
//	 
//	    public Pair(int x, int y)
//	    {
//	        this.x = x;
//	        this.y = y;
//	    }
//	 
//	    @Override
//	    public int compareTo(Pair ob)
//	    {
//	        if(this.x < ob.x)
//	            return -1;
//	        return 1;
//	    }
//	}
	static class Pair{
    	int x;
    	int y;
    	Pair(int x,int y){
    		this.x=x;
    		this.y=y;
    	}
    	@Override
        public int hashCode() {
            final int prime = 31;
           int  result = prime * x + y; 
            return result;
        }
    	
    	 @Override
    	    public boolean equals(Object obj) {
    	        if (this == obj)
    	            return true;
    	        if (obj == null)
    	            return false;
    	        if (getClass() != obj.getClass())
    	            return false;
    	        Pair other = (Pair) obj;
    	        if (x != other.x && y != other.y)
    	            return false;
    	        return true;
    	    }
    	 @Override
    	 public String toString() {
    		 return "{"+String.valueOf(x)+","+String.valueOf(y)+"}";
    	 }
    	
    }
static class BufferInput {
		
		final private int BUFFER_SIZE = 1 << 16;
		
		private DataInputStream din;
		
		private byte[] buffer;
		
		private int bufferPointer, bytesRead;
		
		public BufferInput() {
			din = new DataInputStream(System.in);
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public BufferInput(String file_name) throws IOException {
			din = new DataInputStream(new FileInputStream(file_name));
			buffer = new byte[BUFFER_SIZE];
			bufferPointer = bytesRead = 0;
		}

		public String readLine() throws IOException {
			byte[] buf = new byte[64];
			int cnt = 0, c;
			while ((c = read()) != -1) {
				if (c == '\n')
					break;
				buf[cnt++] = (byte) c;
			}
			return new String(buf, 0, cnt);
		}
		
		public String nextString() throws IOException{
			
			byte c = read();
			while(Character.isWhitespace(c)){
				c = read();
			}
			
			StringBuilder builder = new StringBuilder();
			builder.append((char)c);
			c = read();
			while(!Character.isWhitespace(c)){
				builder.append((char)c);
				c = read();
			}
			
			return builder.toString();
		}
		
		public int nextInt() throws IOException {
			int ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (neg)
				return -ret;
			return ret;
		}
		
		public int[] nextIntArray(int n) throws IOException {
			int arr[] = new int[n];
			for(int i = 0; i < n; i++){
				arr[i] = nextInt();
			}
			return arr;
		}
		public long nextLong() throws IOException {
			long ret = 0;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();
			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');
			if (neg)
				return -ret;
			return ret;
		}
		
		public long[] nextLongArray(int n) throws IOException {
			long arr[] = new long[n];
			for(int i = 0; i < n; i++){
				arr[i] = nextLong();
			}
			return arr;
		}
		
		public char nextChar() throws IOException{
			byte c = read();
			while(Character.isWhitespace(c)){
				c = read();
			}
			return (char) c;	
		}
		public double nextDouble() throws IOException {
			double ret = 0, div = 1;
			byte c = read();
			while (c <= ' ')
				c = read();
			boolean neg = (c == '-');
			if (neg)
				c = read();

			do {
				ret = ret * 10 + c - '0';
			} while ((c = read()) >= '0' && c <= '9');

			if (c == '.') {
				while ((c = read()) >= '0' && c <= '9') {
					ret += (c - '0') / (div *= 10);
				}
			}

			if (neg)
				return -ret;
			return ret;
		}
		public double[] nextDoubleArray(int n) throws IOException {
			double arr[] = new double[n];
			for(int i = 0; i < n; i++){
				arr[i] = nextDouble();
			}
			return arr;
		}
		private void fillBuffer() throws IOException {
			bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
			if (bytesRead == -1)
				buffer[0] = -1;
		}
		private byte read() throws IOException {
			if (bufferPointer == bytesRead)
				fillBuffer();
			return buffer[bufferPointer++];
		}

		public void close() throws IOException {
			if (din == null)
				return;
			din.close();
		}
	}
}
