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.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public final static Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
        for (int t = scanner.nextInt(); t > 0; t--) {
            Main job = new Main();
            System.out.println(job.run());
        }
    }

    private int run() {
        char[] path = scanner.next().toCharArray();
        Set<Long> vis = new HashSet<>();
        int x = 0, y = 0;
        vis.add(0L);
        int ans = 0;
        for (char c: path) {
            int f0 = 0, f1 = 0;
            long k0 = toHashKey(x, y);
            switch (c) {
                case 'N':
                    y++;
                    f0 = 1;
                    f1 = 2;
                    break;
                case 'W':
                    x--;
                    f0 = 3;
                    f1 = 4;
                    break;
                case 'S':
                    y--;
                    f0 = 2;
                    f1 = 1;
                    break;
                case 'E':
                    x++;
                    f0 = 4;
                    f1 = 3;
                    break;
                default:
                    continue;
            }
            long k1 = toHashKey(x, y) * 10 + f1;
            k0 = k0 * 10 + f0;
            if (vis.contains(k1)) {
                ans += 1;
            } else {
                ans += 5;
                vis.add(k0);
                vis.add(k1);
            }
        }
        return ans;
    }

    private long toHashKey(int a, int b) {
        return (long) a * 100000000L + b;
    }
}