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
# Template 1.0
import sys, re, math
from collections import deque, defaultdict, Counter, OrderedDict
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from heapq import heappush, heappop, heapify, nlargest, nsmallest
def STR(): return list(input())
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
def sortListWithIndex(listOfTuples, idx):   return (sorted(listOfTuples, key=lambda x: x[idx]))
def sortDictWithVal(passedDic):
    temp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))
    toret = {}
    for tup in temp:
        toret[tup[0]] = tup[1]
    return toret
def sortDictWithKey(passedDic):
    return dict(OrderedDict(sorted(passedDic.items())))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def change(X, Y, charac):
    if(charac=='N'):
        Y+=1
    elif(charac=='S'):
        Y-=1
    elif(charac=='W'):
        X-=1
    else:
        X+=1
    return X, Y

def dashed(ch):
    if (ch == 'N'):
        chdash = 'S'
    elif (ch == 'S'):
        chdash = 'N'
    elif (ch == 'E'):
        chdash = 'W'
    else:
        chdash = 'E'
    return chdash

t = INT()

while(t!=0):
    s = input()
    ans = 0
    dic = {}
    x=y=0

    # print(dic)
    for ch in s:
        # print(dic)
        if((x,y) not in dic):
            ans+=5
            dic[(x, y)] = []

            dic[(x, y)].append(ch)

            x, y = change(x, y, ch)
            if((x,y) in dic):
                dic[(x, y)].append(dashed(ch))
            else:
                dic[(x,y)] = []
                dic[(x, y)].append(dashed(ch))
        else:
            if(ch in dic[(x, y)]):
                ans+=1
                x, y = change(x, y, ch)
            else:

                ans+=5

                dic[(x, y)].append(ch)
                x, y = change(x,y,ch)
                if ((x, y) in dic):
                    dic[(x, y)].append(dashed(ch))
                else:
                    dic[(x, y)] = []
                    dic[(x, y)].append(dashed(ch))
    print(ans)


    t-=1