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
sides = {'S': [0, -1], 'N': [0, 1],'W': [-1, 0] ,'E': [1, 0]}
s = {'S': 'N', 'N': 'S','W': 'E', 'E': 'W'}

for i in range(int(input())):
    sl = {'S': set(), 'N': set(),'W': set(), 'E': set()}
    cur = [0, 0]
    l = 0
    w = input()
    for ch in w:
        if (cur[0], cur[1]) in sl[ch]:
            l += 1
            cur = list(map(lambda x, y: x+y, cur, sides[ch]))
        else:
            l += 5
            sl[ch].add((cur[0], cur[1]))
            cur = list(map(lambda x, y: x+y, cur, sides[ch]))
            sl[s[ch]].add((cur[0], cur[1]))
    print(l)