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
def join_vecs(a,b):
    out = a.copy()
    for i in range(len(b)):
        out.append(b[i])
    return out

def get_vecs(point, operation):
    curr_point = point.copy()
    if operation == 'N':
        point[1] = point[1] + 1
    if operation == 'S':
        point[1] = point[1] - 1
    if operation == 'E':
        point[0] = point[0] + 1
    if operation == 'W':
        point[0] = point[0] - 1
    
    vec_1 = 'x'.join(list(map(lambda x: str(x),curr_point))) + 'x'.join(list(map(lambda x: str(x),point)))
    vec_2 = 'x'.join(list(map(lambda x: str(x),point))) + 'x'.join(list(map(lambda x: str(x),curr_point)))
    
    return vec_1, vec_2, point

def solve(operations):
    curr_point = [0,0]
    NS_vectors = []
    EW_vectors = []
    k = 0

    for operation in operations:
        vec_1, vec_2, curr_point = get_vecs(curr_point, operation)
        if (operation == 'N') | (operation == 'S'):
                NS_vectors.append(vec_1)
                NS_vectors.append(vec_2)
        if (operation == 'E') | (operation == 'W'):
                EW_vectors.append(vec_1)
                EW_vectors.append(vec_2)
                
    k += int((len(NS_vectors) - len(set(NS_vectors)))/2) + int(len(set(NS_vectors))/2)*5
    k += int((len(EW_vectors) - len(set(EW_vectors)))/2) + int(len(set(EW_vectors))/2)*5
    return str(k)
    
t = int(input())
answers = []
for i in range(t):
    operations = input()
    answers.append(solve(operations))

print("\n".join(answers))