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.lang.*;
import java.io.*;

public class C {
	public static void main (String[] args) throws java.lang.Exception {
		new Solution();
	}
}
class Solution {
	Reader reader;
	PrintWriter out;
	public Solution() {
		reader = new Reader();
		out = new PrintWriter(System.out);
		int t = reader.ni();
		while (reader.hasNext()) {
			run_case();
		}
		out.flush();
	}

	private void run_case() {
		String str = reader.ns();
		Set<String> vis = new HashSet<>();
		int r = 0, c = 0;
		int res = 0;
		for (char ch : str.toCharArray()) {
			// String key = String.valueOf(r) + "_" + String.valueOf(c);
			int tr = 0, tc = 0;
			if (ch == 'N') {
				tr = r - 1;
				tc = c;
			} else if (ch == 'S') {
				tr = r + 1;
				tc = c;
			} else if (ch == 'W') {
				tr = r;
				tc = c - 1;
			} else if (ch == 'E') {
				tr = r;
				tc = c + 1;
			}
			// String tkey = String.valueOf(tr) + "_" + String.valueOf(tc);

			String key = String.valueOf(Math.min(r, tr)) + "_" +
						String.valueOf(Math.min(c, tc)) + "_" +
						String.valueOf(Math.max(r, tr)) + "_" +
						String.valueOf(Math.max(c, tc));

			if (vis.contains(key)) res += 1;
			else res += 5;

			vis.add(key);
			r = tr;
			c = tc;
		}
		out.println(res);
		return;
	}
}


class Reader {
	BufferedReader br;
	StringTokenizer st;
	public Reader(){
		try {
			br = new BufferedReader(new InputStreamReader(System.in));
			st = new StringTokenizer(br.readLine());
		} catch (Exception e) {
			e.printStackTrace();
		}
	}
	public String next() {
		if (st.hasMoreTokens()) return st.nextToken();
		try {
			st = new StringTokenizer(br.readLine());
		} catch (Exception e) {
			e.printStackTrace();
		}
		return st.nextToken();
	}
	public boolean hasNext() {
		try {
			if (!st.hasMoreTokens() && !br.ready()) return false;
			else return true;
		} catch (Exception e) {
			e.printStackTrace();
		}
		return false;
	}
	public int ni() {return Integer.parseInt(this.next());}
	public long nl() {return Long.parseLong(this.next());}
	public String ns() {return this.next();}
}
