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 org.w3c.dom.ls.LSOutput;

import javax.imageio.metadata.IIOMetadataFormatImpl;
import javax.swing.plaf.basic.BasicScrollPaneUI;
import java.util.*;

public class HJFBHHJVNSDJKVNEHFVNSDJICNDCHNh {
    static Scanner s = new Scanner(System.in);
    public static void main(String[] args) {
        int t = s.nextInt();
        for (int gjbnbb = 0; gjbnbb < t; gjbnbb++) {
            char [] a = s.next().toCharArray();
            TreeSet <Pair> set = new TreeSet<>();
            Cor now = new Cor(0, 0);
            int sum = 0;
            for (char value : a) {
                Cor c = new Cor(0, 0);
                switch (value) {
                    case 'S':
                        c = new Cor(now.x, now.y - 1);
                        break;
                    case 'W':
                        c = new Cor(now.x - 1, now.y);
                        break;
                    case 'N':
                        c = new Cor(now.x, now.y + 1);
                        break;
                    case 'E':
                        c = new Cor(now.x + 1, now.y);
                }
                Pair p = new Pair(now, c);
                if (set.contains(p)) {
                    sum++;
                } else {
                    set.add(p);
                    set.add(new Pair(p.y, p.x));
                    sum += 5;
                }
                now = c;
            }
            System.out.println(sum);
        }

    }

    static long pw(int s, long d){
        long ans = 1;
        for (int i = 0; i < d; i++) {
            ans *= s;
        }
        return ans;
    }
}
class Pair implements Comparable<Pair>{
    Cor x;
    Cor y;

    @Override
    public int compareTo(Pair pair) {
        if (x.compareTo(pair.x) == 0){
            return y.compareTo(pair.y);
        }
        else{
            return x.compareTo(pair.x);
        }
    }

    public Pair(Cor x, Cor y) {
        this.x = x;
        this.y = y;
    }
}
class Cor implements Comparable<Cor>{
    public Cor(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public int compareTo(Cor cor) {
        if (this.x == cor.x) return this.y - cor.y;
        else return this.x - cor.x;
    }

    int x;
    int y;
}