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
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque
from math import sqrt, gcd, factorial
# def input(): return sys.stdin.readline()[:-1] # warning not \n
def input(): return sys.stdin.buffer.readline()[:-1]

# n = int(input())



def solve():
    m = defaultdict(int)
    x, y = 0, 0

    ans = 0
    s = input().strip()
    # print(s)
    
    # print(x,y)
    for e in s:

        a, b = x, y

        if e == ord('N'):
            y += 1
        elif e == ord('S'):
            y -= 1
        elif e == ord('E'):
            x += 1
        elif e == ord('W'):
            x -= 1

        l = [(x,y), (a,b)]
        l.sort()
        l = tuple(l)
        if m[l]:
            ans += 1
        else:
            ans += 5
            m[l] = 1
        # print(x, y)

    print(ans)

t = 1
t = int(input())
for case in range(1,t+1):
    ans = solve()
    # print("Case #{}: {} ".format(case, ans))



"""

10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 


"""

