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 sys
from time import *
from math import *
from bisect import bisect_left as bl,bisect_right as br,bisect,insort,insort_left,insort_right
INF = float('inf')
MOD = 998244353
mod = 10**9+7
from collections import Counter as cc , defaultdict as df , OrderedDict as od 
from functools import reduce
def counter(l): return dict(cc(l))
def lcm(a,b): 
    return int((a*b) / gcd(a,b))
def so(x):      return {k: v for k, v in sorted(x.items(), key=lambda item: item[1])}
def rev(l):     return list(reversed(l))
def i3():      return int(sys.stdin.readline())
def i2():      return map(int, sys.stdin.readline().strip().split())
def li():       return list(map(int, sys.stdin.readline().strip().split()))
def i1():    return sys.stdin.readline().strip()
def inputm(n,m):return [li() for i in range(n)]
def zero(n): return [0 for i in range(n)]
def zero2(n,m): return [[0 for i in range(m)] for j in range(n)]
def yes(): print('YES')
def no(): print('NO')
def p(n):
    l=[]
    while n % 2 == 0:
        l.append(2)
        n = n / 2
    for i in range(3,int(sqrt(n))+1,2):
        while n % i== 0:
            l.append(i)
            n = n / i 
    if n > 2:
        l.append(int(n))
    return l
        
def main():
    s=i1()
    n=len(s)
    l=df(int)
    cout=0
    a,b,c,d=0,0,0,0
    for i in s:
        c,d=a,b
        if i=='N':
            a+=1
        elif i=='S':
            a-=1
        elif i=='E':
            b+=1
        elif i=='W':
            b-=1
        if l[(a,b,c,d)] or l[(c,d,a,b)]:
            cout+=1
        else:
            cout+=5
            l[(a,b,c,d)]=1
    print(cout)
            
    
    
            
        
        
    
            
        
    
    
    
        
        
            
            
        
    

            
            
                        
        
        
        
            
    
        
        
    
        
    
    
        
            
            
        
    





if __name__ == "__main__":
    for i in range(i3()):
        main()

#सर्वभूतेष्वभयदस्तं देवा ब्राह्मणं विदुः ॥ भावार्थ : जो व्यक्ति सम्मान दिए जाने अथवा अपमान किये जाने पर न तो प्रसन्न होता है और न ही नाखुश, और जो सभी प्राणियों अभय देता है उसी को देवतागण ब्राह्मण कहते है । नाभिनन्देत मरणं नाभिनन्देत जीवितम् ।
