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 Solution {
    static FastReader in;
    static StringBuilder sb;
    static long mod=1000000007;
    public static void main(String[] args) throws Exception {
        sb = new StringBuilder();
        in = new FastReader();
        int t = in.nextInt();
        while(t-->0)
            solve();
        System.out.print(sb);
    }
    static void solve() throws IOException {
        int i, j;
        String s=in.next();
        HashSet<String> set = new HashSet<>();
        int a=0, b=0, x=0, y=0, n=s.length(), ans=0;
        for(i=0;i<n;i++) {
            char c=s.charAt(i);
            if(c=='N')
                y++;
            else if(c=='E')
                x++;
            else if(c=='S')
                y--;
            else
                x--;
            String p = Integer.toString(x)+" "+Integer.toString(y);
            String q = Integer.toString(a)+" "+Integer.toString(b);
            String aa = p + "  " + q, bb = q + "  " + p;
            if(set.contains(aa) || set.contains(bb))
                ans++;
            else {
                set.add(aa);
                ans+=5;
            }
            a=x;
            b=y;
            //sb.append(set+"\n");
        }
        sb.append(ans+"\n");
    }
}
//Collections.sort(ar, new sortbyX());
class Pair { 
    int x; 
    int y; 
    public Pair(int x, int y) 
    {
        this.x = x; 
        this.y = y; 
    } 
}
class sortbyX implements Comparator<Pair> { 
    public int compare(Pair a, Pair b) 
    { 
        return a.x - b.x; 
    } 
}
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;
    }
}
/*
excitement or passion motivated you to achieve something outstanding.

When I was in the first year of my college, I heard of a global level contest on competiitve programming namely 
SnackDown. By that time I had barely started competitive programming. But I was very curious and excited so i 
decided to participate along with one of my friends. In the qulaification round we easily solved the problems 
secured a good rank to move to next round. But then the real contest begin. The next round was held for 2 days 
and there were many problems of various levels ranging from easy to hard. I was finding a hard time to keep up 
with the level of competition. But I kept on trying hard along with the combined effort of my teammate and 
eventually we qualified in top 3000 teams globally and qualified in the next round. I was very happy back then 
and it was only for my passion, that I was able to achieve such a feat.


partner leaves a challenging project due to personal reason. what will i do?

*/
