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 getLines(num,p):
  n = num if num <= pow(10,p) else pow(10,p)
  inputLines = []
  for i in range(0,n):
    line = input()
    if line:
      inputLines.append(line)
    else:
        break
  return inputLines


def notZeroPow(num,p):
  return True if num >= 1 and num <= pow(10,p)  else False
    
def minPair(a, b):
	return   a  if a[0] + a[1] < b[0] + b[1] else b

def maxPair(a, b):
  return  a if  a[0] + a[1] > b[0] + b[1] else b

def setAdd(s, x):
  l = len(s)
  s.add(x)
  return len(s) != l


def getSum(text):
  points = {}
  cur = [0,0]
  sum = 0
  for c in text:
    nxt = [cur[0],cur[1]]

    if c == "N":
      nxt[0] += 1
    if c == "S":
      nxt[0] -= 1
    if c == "W":
      nxt[1] += 1
    if c == "E":
      nxt[1] -= 1

    l = minPair(cur,nxt)
    h = maxPair(cur,nxt)

    sp = str(l[0]) + str(l[1]) + str(h[0]) + str(h[1])
    if not sp in points:
      sum += 5
      points[sp] = 1
    else:
      sum += 1
    cur = [nxt[0],nxt[1]]
    
  return sum

rc = int(input())
lines = getLines(rc,4)
   
results = []
for e in lines:
    sum = getSum(e)
    results.append(sum)

for e in results:
    print(e)


