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.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Submit {
    public static void main(String args[]) throws IOException{
        process();
    }
    public static void process() throws IOException{
        BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        int T=Integer.parseInt(in.readLine());
        for(int t=0;t<T;t++){
            char arr[]=in.readLine().toCharArray();
            int n=arr.length;
            HashSet<String> set=new HashSet<>();
            int x=0;
            int y=0;
            int x1=0;
            int y1=0;
            long ans=0;
            for(int i=0;i<n;i++){
                x1=x;
                y1=y;
                if(arr[i]=='N')
                    y++;
                else if(arr[i]=='S')
                    y--;
                else if(arr[i]=='E')
                    x++;
                else
                    x--;
                String str=x+" "+y+" "+x1+" "+y1;
                String str1=x1+" "+y1+" "+x+" "+y;
                if(set.contains(str) || set.contains(str1))
                    ans++;
                else{
                    ans+=5;
                    set.add(str1);
                }
            }
            System.out.println(ans);
        }
    }
}
