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 javax.print.attribute.HashAttributeSet;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Objects;
import java.util.StringTokenizer;

public class TaskC {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        PrintWriter pw = new PrintWriter(System.out);
        
        try {
            int t = Integer.parseInt(br.readLine());
            while(t-->0) {
                int x = 0;
                int y = 0;
                int a = 0;
                int b = 0;
                char[] c = br.readLine().toCharArray();
                HashSet<Pair> hs = new HashSet<>();
                int cost = 0;
                for(int i=0 ; i<c.length ; i++) {
                    if(c[i] == 'S') y--;
                    else if(c[i] == 'N') y++;
                    else if(c[i] == 'W') x--;
                    else x++;
                    Pair p1 = new Pair(x, y, a, b);
                    Pair p2 = new Pair(a, b, x, y);
                    if(hs.contains(p1) || hs.contains(p2)) {
                        cost++;
                    }
                    else {
                        cost += 5;
                        hs.add(p1);
                        hs.add(p2);
                    }
                    a = x;
                    b = y;

                }

                pw.println(cost);
            }
        }
        finally {
            pw.flush();
            pw.close();
        }
    }
}

class Pair {
    int a;
    int b;
    int c;
    int d;
    Pair(int w, int x, int y, int z) {
        a = w;
        b = x;
        c = y;
        d = z;
    }

    public boolean equals(Object ob) {
        if(ob instanceof Pair) {
            Pair p = (Pair) ob;
            return p.a == this.a && p.d == this.d && p.c == this.c && p.b == this.b;
        }
        else return false;
    }

    public int hashCode() {
        return Objects.hash(a, b, c, d);
    }
}
