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
/**
 * 
 */
//package codeforces;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.Objects;
import java.util.Set;
import java.util.Stack;
import java.util.stream.Collectors;
import java.util.stream.Stream;

/**
 * @author shidey
 *
 */
public class Skier {

    public static int calcDistance(String path) {
	if (Objects.isNull(path) || path.isEmpty())
	    throw new IllegalArgumentException();

	Set<Character> allowed = Stream.of('N', 'S', 'E', 'W').collect(Collectors.toSet());

	char[] segments = path.toCharArray();
	Stack<Character> stack = new Stack<>();
	int result = 0;
	Pos pos = new Pos(0, 0);
	Set<Segment> visited = new HashSet<>();

	for (char ch : segments) {
	    if (!allowed.contains(ch))
		continue;
	    //if (!stack.isEmpty() && isReverse(stack.peek(), ch))
		//result += 1;
	    Segment visit = move(ch, pos);
	    pos = visit.end;
	    Segment revisit = new Segment(visit.end, visit.start);
	    if(visited.contains(visit) || visited.contains(revisit)) {
		result += 1;
	    }
	    else {

		result += 5;
		//stack.push(ch);
		visited.add(visit);
		visited.add(revisit);
	    }
	}

	return result;
    }

    public static Segment move(char direction, Pos prev) {
	
	if (direction == 'E')
	    return new Segment(prev, new Pos(prev.x, prev.y + 1));
	if (direction == 'W')
	    return new Segment(prev, new Pos(prev.x, prev.y - 1));
	if (direction == 'S')
	    return new Segment(prev, new Pos(prev.x + 1, prev.y));
	if (direction == 'N')
	    return new Segment(prev, new Pos(prev.x - 1, prev.y));

	return null;
    }

    private static boolean isReverse(char prev, char curr) {
	if (prev == 'S' && curr == 'N')
	    return true;

	if (prev == 'N' && curr == 'S')
	    return true;

	if (prev == 'E' && curr == 'W')
	    return true;

	if (prev == 'W' && curr == 'E')
	    return true;

	return false;
    }

    static class Segment {
	Pos start, end;

	public Segment(Pos start, Pos end) {
	    this.start = start;
	    this.end = end;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see java.lang.Object#hashCode()
	 */
	@Override
	public int hashCode() {
	    final int prime = 31;
	    int result = 1;
	    result = prime * result + ((end == null) ? 0 : end.hashCode());
	    result = prime * result + ((start == null) ? 0 : start.hashCode());
	    return result;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see java.lang.Object#equals(java.lang.Object)
	 */
	@Override
	public boolean equals(Object obj) {
	    if (this == obj)
		return true;
	    if (obj == null)
		return false;
	    if (!(obj instanceof Segment))
		return false;
	    Segment other = (Segment) obj;
	    if (end == null) {
		if (other.end != null)
		    return false;
	    } else if (!end.equals(other.end))
		return false;
	    if (start == null) {
		if (other.start != null)
		    return false;
	    } else if (!start.equals(other.start))
		return false;
	    return true;
	}

    }

    static class Pos {
	int x, y;

	public Pos(int x, int y) {
	    this.x = x;
	    this.y = y;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see java.lang.Object#hashCode()
	 */
	@Override
	public int hashCode() {
	    final int prime = 31;
	    int result = 1;
	    result = prime * result + x;
	    result = prime * result + y;
	    return result;
	}

	/*
	 * (non-Javadoc)
	 * 
	 * @see java.lang.Object#equals(java.lang.Object)
	 */
	@Override
	public boolean equals(Object obj) {
	    if (this == obj)
		return true;
	    if (obj == null)
		return false;
	    if (!(obj instanceof Pos))
		return false;
	    Pos other = (Pos) obj;
	    if (x != other.x)
		return false;
	    if (y != other.y)
		return false;
	    return true;
	}

    }
    
    
    public static void testSegments() {
	Pos p1 = new Pos(1,1);
	Pos p2 = new Pos(1,2);
	Segment s1 = new Segment(p1,p2);
	Segment s2 = new Segment(p2,p1);
	System.out.println(s1.equals(s2));
	System.out.println(s1.hashCode());
	System.out.println(s2.hashCode());

    }

    public static void main1(String[] args) {
	testSegments();
    }
    
    public static void main(String[] args) throws Exception {
	BufferedReader reader = null;
	try {
	    reader = new BufferedReader(new InputStreamReader(System.in));
	    int tests = Integer.parseInt(reader.readLine());
	    if (tests <= 0)
		throw new InputMismatchException();

	    for (int i = 0; i < tests; i++)
		System.out.println(calcDistance(reader.readLine()));
	} catch (Exception e) {
	    throw e;
	} finally {
	    try {
		if (null != reader)
		    reader.close();
	    } catch (Exception e1) {
		throw e1;
	    }
	}
    }

}
