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.Map;
import java.util.TreeMap;

public class Test2 {
    public static void main(String[] args) throws IOException {
        Map<Nodes,Integer> map=new TreeMap<>();
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        String test_numS=bf.readLine();
        int test_num=Integer.parseInt(test_numS);
        int No=0;

        while(test_num>0){
            map.clear();
            map.put(new Nodes(0,0,0,0),No);
            No++;
            String directionS=bf.readLine();
            char []direction=directionS.toCharArray();
            int x=0,y=0,prex=0,prey=0;
            int time=0;
            for (int i = 0; i < direction.length; i++) {
                prex=x;
                prey=y;
                switch (direction[i]){
                    case 'N':
                        x--;
                        break;
                    case 'S':
                        x++;
                        break;
                    case 'W':
                        y--;
                        break;
                    case 'E':
                        y++;
                        break;
                }
                Nodes nodes1=new Nodes(x,y,prex,prey);
                Nodes nodes2=new Nodes(prex,prey,x,y);
                if (!(map.containsKey(nodes1))&&!(map.containsKey(nodes2))){
                    map.put(nodes1,No);No++;
                    map.put(nodes2,No);No++;
                    time+=5;
                }else time+=1;
            }
            test_num--;
            System.out.println(time);
        }
    }
}
class Nodes implements Comparable<Nodes>{
    int x=0,y=0,prex=0,prey=0;
    public Nodes(){
    }
    public Nodes(int x,int y,int prex,int prey){
        this.x=x;
        this.y=y;
        this.prex=prex;
        this.prey=prey;
    }
    public int compareTo(Nodes n) {
        if (this.x!=n.x)
            return this.x-n.x;
        else if(this.y!=n.y)
            return this.y-n.y;
        else if (this.prex!=n.prex)
            return this.prex-n.prex;
        else return this.prey-n.prey;
    }
    /*public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (!(obj instanceof Nodes))
            return false;
        Nodes node = (Nodes) obj;
        if (this.x != node.x)
            return false;
        else if (this.y != node.y)
            return false;
        else if (this.prex != node.prex)
            return false;
        else if (this.prey != node.prey)
            return false;
        else return true;
        /*if (this.prey == node.prey && this.prex == node.prex && this.x == node.x && this.y == node.y) {
            return true;
        } else return false;*/
    //}

}