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
//package com.company;

import javafx.util.Pair;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Scanner;

public class CF_1351_C {
    public static void main(String args[]) {
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        while(t-->0) {
            String s=sc.next();
            HashMap<Pair<Integer,Integer>,HashSet<Pair<Integer,Integer>>> hm=new HashMap<>();
            int x=0;
            int y=0;
            int sum=0;
            int ch[]=new int[26];
            ch['N'-'A']=0;
            ch['W'-'A']=1;
            ch['E'-'A']=2;
            ch['S'-'A']=3;
            int dy[]={1,0,0,-1};
            int dx[]={0,-1,1,0};
//            int sum=0;
            Pair<Integer,Integer> pos=new Pair<>(x,y);
            for(int i=0;i<s.length();++i) {
                char c=s.charAt(i);
                int new_x=x+dx[ch[c-'A']];
                int new_y=y+dy[ch[c-'A']];
                Pair<Integer,Integer> new_pos=new Pair<>(new_x,new_y);
                if(hm.containsKey(pos)&&hm.get(pos).contains(new_pos))
                    sum++;
                else
                    sum+=5;
                if(!hm.containsKey(pos))
                    hm.put(pos,new HashSet<>());
                if(!hm.containsKey(new_pos))
                    hm.put(new_pos,new HashSet<>());
                hm.get(pos).add(new_pos);
                hm.get(new_pos).add(pos);
                pos=new_pos;
                x=new_x;
                y=new_y;
            }
            System.out.println(sum);
        }
    }
}
