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 C 
{	
	
	public static void main(String[] args)throws IOException 
	{	
		FastReader f=new FastReader();
		StringBuffer sb=new StringBuffer();
		
		int test=f.nextInt();
		while(test-->0)
		{	
			Set<String> set=new HashSet<>();
			String s=f.next();
			
			int x=0,y=0;
			long count=0;
			for(int i=0;i<s.length();i++)
			{	
				int prevx=x,prevy=y;
				
				char ch=s.charAt(i);
				if(ch=='N')
					y++;
				if(ch=='S')
					y--;
				if(ch=='E')
					x++;
				if(ch=='W')
					x--;
				
				String opt1=(x+","+y+" - "+prevx+","+prevy);
				String opt2=(prevx+","+prevy+" - "+x+","+y);
				
				if(set.contains(opt1) || set.contains(opt2))
					count++;
				else
				{
					count+=5;
					set.add(opt1);
				}
			}
			sb.append(count+"\n");
		}
		System.out.println(sb);
	}
}
class FastReader 
{ 
	BufferedReader br; 
    StringTokenizer st; 

    public FastReader() {
    	br = new BufferedReader(new
                 InputStreamReader(System.in)); 
    }
    String next() { 
        while (st == null || !st.hasMoreElements()) { 
            try{ 
                st = new StringTokenizer(br.readLine()); 
	            } 
	            catch (IOException  e) { 
	                e.printStackTrace(); 
	            } 
	    } 
	    return st.nextToken(); 
	} 
	int nextInt() { 
		return Integer.parseInt(next()); 
	} 
	long nextLong() { 
		return Long.parseLong(next()); 
	} 
	double nextDouble() { 
	    return Double.parseDouble(next()); 
	} 
	String nextLine() { 
	    String str = ""; 
	    try{ 
	        str = br.readLine(); 
	    } 
	    catch (IOException e) { 
	            e.printStackTrace(); 
	    } 
	    return str; 
    } 
} 
