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.*;

public class Main {

    public Main() {
    }

    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }

    private void solve() {

        Scanner sc = new Scanner( System.in);
        int tests = sc.nextInt();
        while ( tests > 0){

            solution(sc, tests);
            tests--;
        }

        sc.close();
    }

    private void solution( Scanner sc, int testCase) {

        String s = sc.next();

        int result = 0;
        HashMap<String, Integer> map = new HashMap<String, Integer>();

        int a = 0, b = 0;

        for( int i=0; i<s.length(); i++ ) {

            char c = s.charAt(i);

            if( c == 'N') {

                String t1 = "x"+a+"-"+a+"y"+b+"-"+(b-1);
                String t2 = "x"+a+"-"+a+"y"+(b-1)+"-"+b;

                b--;
                if( map.containsKey(t1) || map.containsKey(t2)) result++;
                else{
                    result += 5;
                    map.put( t1,1 );
                    map.put( t2,1 );
                }
            }
            else if( c == 'S') {

                String t1 = "x"+a+"-"+a+"y"+b+"-"+(b+1);
                String t2 = "x"+a+"-"+a+"y"+(b+1)+"-"+b;

                b++;
                if( map.containsKey(t1) || map.containsKey(t2)) result++;
                else{
                    result += 5;
                    map.put( t1,1 );
                    map.put( t2,1 );
                }
            }
            else if( c == 'E') {

                String t1 = "x"+a+"-"+(a+1)+"y"+b+"-"+b;
                String t2 = "x"+(a+1)+"-"+a+"y"+b+"-"+b;

                a++;
                if( map.containsKey(t1) || map.containsKey(t2)) result++;
                else{
                    result += 5;
                    map.put( t1,1 );
                    map.put( t2,1 );
                }
            }
            else if( c == 'W') {

                String t1 = "x"+a+"-"+(a-1)+"y"+b+"-"+b;
                String t2 = "x"+(a-1)+"-"+a+"y"+b+"-"+b;

                a--;
                if( map.containsKey(t1) || map.containsKey(t2)) result++;
                else{
                    result += 5;
                    map.put( t1,1 );
                    map.put( t2,1 );
                }
            }


        }
        System.out.println(result);
    }

}
