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

public class Ishu
{
	public static void main(String[] args)
	{
	Scanner scan=new Scanner(System.in);
	int t;
	t = scan.nextInt();
	while(t-- > 0)
		{
		int ans = 0;
		Map<String, Boolean> map = new HashMap<String, Boolean>();
		String str = scan.next();
		int i;
		int x = 0,y = 0;
		for(i=0;i<str.length();++i)
			{
			int tx = x, ty = y;
			switch(str.charAt(i))
				{
				case 'N': ++y;
						  break;
				case 'S': --y;
						  break;
				case 'E': ++x;
						  break;
				case 'W': --x;
						  break;
				}
			Node node1 = new Node(tx,ty,x,y);
			Node node2 = new Node(x,y,tx,ty);
	
			if(map.containsKey(node1.getID()) || map.containsKey(node2.getID()))
				++ans;
			else
				{
				ans += 5;
				map.put(node1.getID(),true);
				map.put(node2.getID(),true);
				}
			}
		System.out.println(ans);
		}	
	}
}
class Node
{
int x1,x2,y1,y2;
String id;
Node(int x1, int y1, int x2, int y2)
	{
	this.x1 = x1;
	this.x2 = x2;
	this.y1 = y1;
	this.y2 = y2;
	setID();
	}
	
private void setID()
	{
	id = "";
	id += String.valueOf(x1) + ",";
	id += String.valueOf(y1) + ",";
	id += String.valueOf(x2) + ",";
	id += String.valueOf(y2) + ",";
	}
	
public String getID()
	{
	return id;
	}
}
