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.InputStream;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.StringTokenizer;


public class A {
	
	public void solve() {
		int t = in.nextInt();
		
		while (t-- > 0) {
			int result = 0;
			String s = in.nextLine();

			HashSet<Path> vis = new HashSet<Path>();
			Pair currP = new Pair(0, 0);
			for (int i = 0; i < s.length(); ++i) {
				Pair preP = new Pair(currP);
				switch (s.charAt(i)) {
				case 'N':
					currP.y++;
					break;
				case 'E':
					currP.x++;
					break;
				case 'W':
					currP.x--;
					break;
				case 'S':
					currP.y--;
					break;
				}
				
				Path p = new Path(preP, currP);
				if (vis.contains(p)) {
					result++;
				} else {
					result += 5;
					vis.add(p);
					vis.add(new Path(currP, preP));
				}
			}
			out.println(result);
		}
	}

	FastReader in;
	PrintWriter out;

	public void run() {
		in = new FastReader(System.in);
		out = new PrintWriter(System.out);
		solve();
		out.close();
	}

	public static void main(String[] args) {
		new A().run();
	}

	static class FastReader {
		BufferedReader br;
		StringTokenizer st;

		FastReader(InputStream stream) {
			br = new BufferedReader(new InputStreamReader(stream));
		}

		private String next() {
			if (st == null || !st.hasMoreElements()) {
				st = new StringTokenizer(this.nextLine());
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(this.next());
		}

		long nextLong() {
			return Long.parseLong(this.next());
		}

		double nextDouble() {
			return Double.parseDouble(this.next());
		}

		String nextLine() {
			String line = null;
			try {
				line = br.readLine();
			} catch (IOException e) {

			}
			return line;
		}
	}

}

class Pair {
	public int x, y;
	
	Pair(int x, int y) {
		this.x = x; 
		this.y = y;
	}
	
	Pair(Pair p) {
		this.x = p.x;
		this.y = p.y;
	}
	
	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + x;
		result = prime * result + 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)
			return false;
		if (y != other.y)
			return false;
		return true;
	}
}

class Path {
	Pair a, b;
	
	Path(Pair a, Pair b) {
		this.a = new Pair(a);
		this.b = new Pair(b);
	}

	@Override
	public boolean equals(Object obj) {
		if (this == obj)
			return true;
		if (obj == null)
			return false;
		if (getClass() != obj.getClass())
			return false;
		Path other = (Path) obj;
		if (a == null) {
			if (other.a != null)
				return false;
		} else if (!a.equals(other.a))
			return false;
		if (b == null) {
			if (other.b != null)
				return false;
		} else if (!b.equals(other.b))
			return false;
		return true;
	}

	@Override
	public int hashCode() {
		final int prime = 31;
		int result = 1;
		result = prime * result + ((a == null) ? 0 : a.hashCode());
		result = prime * result + ((b == null) ? 0 : b.hashCode());
		return result;
	}

}