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.*;
import java.io.*;
public class Task {
     
static BufferedReader s1;
static BufferedWriter out;
static String read() throws IOException{String line="";while(line.length()==0){line=s1.readLine();continue;}return line;}
static int int_v (String s1){return Integer.parseInt(s1);}
static long long_v(String s1){return Long.parseLong(s1);}
static int[] int_arr() throws IOException{String[] a=read().split(" ");int[] b=new int[a.length];for(int i=0;i<a.length;i++){b[i]=int_v(a[i]);}return b;}
static long[] long_arr() throws IOException{String[] a=read().split(" ");long[] b=new long[a.length];for(int i=0;i<a.length;i++){b[i]=long_v(a[i]);}return b;}
static void assign(){s1=new BufferedReader(new InputStreamReader(System.in));out=new BufferedWriter(new OutputStreamWriter(System.out));}
static int gcd(int a,int b){if(b==0){return a;}return gcd(b,a%b);}
 
static class edge{
    int x1,y1,x2,y2;
    edge(int x,int y, int z, int w){
        x1=x;y1=y;x2=z;y2=w;
    }
}
static int f(edge e1, edge e2){
    if(e1.x1==e2.x1&&e1.y1==e2.y1){
        if(e1.x2==e2.x2){return e1.y2-e2.y2;}
        return e1.x2-e2.x2;
    }
    if(e1.x1==e2.x1){return e1.y1-e2.y1;}
        return e1.x1-e2.x1;
}
  public static void main(String args[]) throws  IOException {
         assign();
              int t=int_v(read()),cn=1;
              while(t--!=0){
                String s=read();
                int x=0,y=0,res=0,n=s.length();
                TreeSet<edge> map=new TreeSet<>((a,b)->f(a,b));
                int prex=0,prey=0;
                for(int i=0;i<s.length();i++){
                    char c=s.charAt(i);
                    if(c=='N'){y++;}
                    else if(c=='S'){y--;}
                    else if(c=='E'){x++;}
                    else{x--;}
                   edge e=new edge(prex,prey,x,y);
                   edge e1=new edge(x,y,prex,prey);
                   if(map.contains(e)){
                        res++;
                        if(!map.contains(e1)){map.add(e1);}
                   }
                   else if(map.contains(e1)){
                        res++;
                        map.add(e);
                   }
                   else{
                         res+=5;
                          map.add(e); map.add(e1);
                   }
                   
                   prex=x;prey=y;
                }
               out.write(res+"\n");
               
            }
              out.flush();
    }
           
}