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.omg.CORBA.INTERNAL;

import java.io.*;
import java.util.*;

public class C {
    public static void main(String[] args) throws IOException {
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        InputReader in=new InputReader(System.in);
        int t=in.nextInt();
        while (t-->0){
            Map<Integer, Map<Integer,List<Integer[]>>> map=new HashMap<>();
            String next = in.next();
            int x=0,y=0,lastx=0,lasty=0;
            long res=0;
            for(int i=0;i<next.length();i++){
                switch (next.charAt(i)){
                    case 'S':
                        x++;
                        break;
                    case 'N':
                        x--;
                        break;
                    case 'W':
                        y--;
                        break;
                    case 'E':
                        y++;
                        break;
                }

                Map<Integer,List<Integer[]>> temp = map.get(lastx);
                if(temp==null){
                    temp=new HashMap<>();
                    map.put(lastx,temp);
                }
                boolean flag=false;
                List<Integer[]> integers = temp.get(lasty);
                if(integers==null){
                    integers=new ArrayList<>();
                    temp.put(lasty,integers);
                }else{
                    for(Integer[] arr:integers){
                        if(arr[0]==x&&arr[1]==y) flag=true;
                    }
                }

                if(flag)res+=1;
                else{
                    res+=5;
                    integers.add(new Integer[]{x,y});
                    solve(lastx,lasty,x,y,map);
                    solve(x,y,lastx,lasty,map);
                }
                lastx=x;
                lasty=y;
            }
            out.println(res);
        }
        out.flush();
    }
    public static  void solve(int lastx,int lasty,int x,int y,Map<Integer, Map<Integer,List<Integer[]>>> map){
        Map<Integer, List<Integer[]>> map1 = map.get(lastx);
        if(map1==null){
            map1=new HashMap<>();
            map.put(lastx,map1);
        }
        List<Integer[]> list = map1.get(lasty);
        if(list==null){
            list=new ArrayList<>();
            map1.put(lasty,list);
        }
        boolean flag=false;
        for(Integer []arr:list){
            if(arr[0]==x&&arr[1]==y) flag=true;
        }
        if(!flag)
            list.add(new Integer[]{x,y});
    }
    static class InputReader{
        private BufferedReader in;
        private StringTokenizer tokenizer;
        public InputReader(InputStream stream){
            in = new BufferedReader(new InputStreamReader(stream),32768);
            tokenizer = null;
        }
        public String next() throws IOException{
            while(tokenizer==null || !tokenizer.hasMoreTokens()){
                tokenizer = new StringTokenizer(in.readLine());
            }
            return tokenizer.nextToken();
        }
        public Long nextLong() throws IOException {
            String next = next();
            return Long.valueOf(next);
        }
        public int nextInt() throws IOException{
            return Integer.valueOf(next());
        }
    }
}