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
# ░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
# ░░░░░░░▄▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▄░░░░░░
# ░░░░░░█░░▄▀▀▀▀▀▀▀▀▀▀▀▀▄░░█░░░░░
# ░░░░░░█░█░░▀░░░░░░░░▀░░█░█░░░░░
# ░░░░░░█░█░░░▀░░░░░░▀░░░█░█░░░░░
# ░░░░░░█░█░░░░▀░░░░▀░░░░█░█░░░░░
# ░░░░░░█░█▄░░░░▀░░▀░░░░▄█░█░░░░░
# ░░░░░░█░█░░░░░░██░░░░░░█░█░░░░░
# ░░░░░░█░▀░░░░░░░░░░░░░░▀░█░░░░░
# ░░░░░░█░░░░░░  ░░░░░  ░░░█░░░░░
# ░░░░░░█░░░░░░ ░ ░░░ ░ ░░░█░░░░░
# ░░░░░░▀░░░░░░ ░░ ░ ░░ ░░░▀░░░░░
# ░░░░░░░░░░░░░ ░░░ ░░░ ░░░░░░░░░

MOD =  1000000007
mod = 10009
#import time
#import heapq
import math
#import string
#import bisect
#import collections
#import itertools
 
def primeseive(n):
    prime = [True for i in range(n+1)]
    p=2
    while p*p<=n:
        if prime[p]==True:
            for i in range(p*p,n+1,p):
                prime[i]=False
        p+=1
    ans = [i for i in range(2,n+1) if prime[i]]
    print(ans)

def checkprime(n):
    if n == 2: return True
    if n % 2 == 0 or n <= 1: return False
    sqr = int(math.sqrt(n)) + 1
    for d in range(3, sqr, 2):
        if n % d == 0: return False
    return True

def primeFactors(n): 
    prime = set()
    while n % 2 == 0: 
        prime.add(2)
        n = n//2
    for i in range(3,int(math.sqrt(n))+1,2): 
        while n % i== 0: 
            prime.add(i)
            n = n//i 
    if n > 2: 
        prime.add(n)
    return list(prime)

def sort_dict(key_value):
    return sorted(key_value.items(), key = lambda kv:(kv[1], kv[0]))

def xymodm(x,y,m):
    res = 1
    x=x%m
    if x==0:
        return 0
    while y>0:
        if y&1:
            res =(res*x)%m
        y = y//2
        x = (x*x)%m
    return res

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

def subarray(a):
    sub = [[]]
    for item in sorted(a):
        sub += [ prevsub + [item] for prevsub in sub]
    return sorted(sub)

def check(a,b,c,d):
    ans = 0
    cnt = b
    ind = 0.0
    flag =True
    if a<=b:
        ans = b
    elif a>b:
        if (c-d)<0:
            ans = -1
        else:
            ind = (a-b)/(c-d)
            #print("(a-b)/c-d = ",ind)
            ans = math.ceil(ind)
            #print("multipler : = ",ans)
            ans = ans*c+b
    print(ans)
#------------------------------------------------
def solve(s):
    dic = {}
    x = 0
    y = 0
    ans= 0
    dic[(x,y)] = 1
    for i in s:
        inix = x
        iniy = y
        if i == "N":
            y+=1
        elif i == "S":
            y-=1
        elif i == "W":
            x-=1
        elif i == "E":
            x+=1
        if (inix,iniy,x,y) in dic:
            ans+=1
        else:
            dic[(inix,iniy,x,y)] = 1
            dic[(x,y,inix,iniy)] = 1
            ans+=5
    print(ans)

    


for i in range(int(input())):
    #x,y,l,r= map(int,input().split())
    #n,k= map(int,input().split())
    #a,b= map(int,input().split())
    #n = int(input())
    #a = list(map(int,input().split()))
    #b = list(map(int,input().split()))
    #l,r= map(int,input().split())
    #n = int(input())
    s = input()
    #sa = list(map(str,input().split()))
    #b = list(map(int,input().split()))
    #st = time.process_time()
    solve(s)
    #print(s)
    #pt = solve(s)
    #print(pt)
    #print("yes" if pt==1 else "no")
    #print("Linear : ",time.process_time() - st)
    #print("Case #%d: %d" % (t, ans))