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.*;
import java.math.*;
import java.lang.*;
import static java.lang.Math.*;

public class Main implements Runnable 
{
	static class InputReader 
	{
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;
		private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		public InputReader(InputStream stream) 
		{
			this.stream = stream;
		}
		
		public int read()
		{
			if (numChars==-1) 
				throw new InputMismatchException();
            
			if (curChar >= numChars) 
			{
				curChar = 0;
				try
				{
					numChars = stream.read(buf);
				}
				catch (IOException e)
				{
					throw new InputMismatchException();
				}
                
				if(numChars <= 0)               
					return -1;
			}
			return buf[curChar++];
		}
     
		public String nextLine()
		{
			String str = "";
			try
			{
				str = br.readLine();
			}
			catch (IOException e)
			{
				e.printStackTrace();
			}	
			return str;
		}
		public int nextInt() 
		{
			int c = read();
            
			while(isSpaceChar(c)) 
				c = read();
		
			int sgn = 1;
        
			if (c == '-') 
			{
				sgn = -1;
				c = read();
			}
            
			int res = 0;
			do
			{
				if(c<'0'||c>'9') 
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			}
			while (!isSpaceChar(c)); 
        
			return res * sgn;
		}
        
		public long nextLong() 
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = read();
			}
			long res = 0;
			
			do 
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			}	
			while (!isSpaceChar(c));
				return res * sgn;
		}
		
		public double nextDouble() 
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = read();
			}
			double res = 0;
			while (!isSpaceChar(c) && c != '.') 
			{
				if (c == 'e' || c == 'E')
					return res * Math.pow(10, nextInt());
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			}
			if (c == '.') 
			{
				c = read();
				double m = 1;
				while (!isSpaceChar(c))
				{
					if (c == 'e' || c == 'E')
						return res * Math.pow(10, nextInt());
					if (c < '0' || c > '9')
						throw new InputMismatchException();
					m /= 10;
					res += (c - '0') * m;
					c = read();
				}
			}
			return res * sgn;
		}
    
		public String readString() 
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do 
			{
				res.appendCodePoint(c);
				c = read();
			} 
			while (!isSpaceChar(c));
            
			return res.toString();
		}
     
		public boolean isSpaceChar(int c) 
		{
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
     
		public String next()
		{
			return readString();
		}
        
		public interface SpaceCharFilter
		{
			public boolean isSpaceChar(int ch);
		}
	}
	public static void main(String args[]) throws Exception 
	{
		new Thread(null, new Main(),"Main",1<<27).start();
	}	
	
	public void run(){
        InputReader sc=new InputReader(System.in);
        PrintWriter out=new PrintWriter(System.out);
        int t=sc.nextInt();
        for(int h=0;h<t;h++)
        {
            String s=sc.next();
            long ans=0;
            int xc=0,yc=0;
            HashSet<ArrayList<Integer>>set=new HashSet<ArrayList<Integer>>();
            for(int i=0;i<s.length();i++)
            {
                if(s.charAt(i)=='N')
                {
                    yc=yc+1;
                    ArrayList<Integer>arr=new ArrayList<Integer>();
                    arr.add(xc);arr.add(yc);arr.add(xc);arr.add(yc-1);
                    ArrayList<Integer>arr1=new ArrayList<Integer>();
                    arr1.add(xc);arr1.add(yc-1);arr1.add(xc);arr1.add(yc);
                    if(set.contains(arr1))
                    {
                        ans=ans+1;
                    }
                    else{

                    ans=ans+5;
                    }
                    set.add(arr);
                    set.add(arr1);
                }
                else if(s.charAt(i)=='S')
                {
                    yc=yc-1;
                    ArrayList<Integer>arr=new ArrayList<Integer>();
                    arr.add(xc);arr.add(yc);arr.add(xc);arr.add(yc+1);
                    ArrayList<Integer>arr1=new ArrayList<Integer>();
                    arr1.add(xc);arr1.add(yc+1);arr1.add(xc);arr1.add(yc);
                    if(set.contains(arr1))
                    {
                        ans=ans+1;
                    }
                    else{
                        
                    ans=ans+5;
                    }
                    set.add(arr);
                    set.add(arr1);
                }
                else if(s.charAt(i)=='W')
                {
                    xc=xc-1;
                    ArrayList<Integer>arr=new ArrayList<Integer>();
                    arr.add(xc);arr.add(yc);
                    arr.add(xc+1);arr.add(yc);
                    ArrayList<Integer>arr1=new ArrayList<Integer>();
                    arr1.add(xc+1);arr1.add(yc);
                    arr1.add(xc);arr1.add(yc);
                    if(set.contains(arr1))
                    {
                        ans=ans+1;
                    }
                    else{
                    
                    ans=ans+5;
                    }
                    set.add(arr);
                    set.add(arr1);
                }
                else if(s.charAt(i)=='E')
                {
                    xc=xc+1;
                    ArrayList<Integer>arr=new ArrayList<Integer>();
                    arr.add(xc);arr.add(yc);
                    arr.add(xc-1);arr.add(yc);
                    ArrayList<Integer>arr1=new ArrayList<Integer>();
                    arr1.add(xc-1);arr1.add(yc);
                    arr1.add(xc);arr1.add(yc);
                    if( set.contains(arr1))
                    {
                        ans=ans+1;
                    }
                    else{
                        
                    ans=ans+5;
                    }
                    set.add(arr);
                    set.add(arr1);
                }
                
            }
            out.println(ans);
        }
        out.flush();
		out.close();
	}
}

