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
from sys import stdin, stdout
cin = stdin.readline
cout = stdout.write

for _ in range(int(cin())):
	s = cin()[:-1]
	
	d = {(0,0): 1}
	x = y = ans = 0
	
	for i in range(len(s)):
		a = x
		b = y
		y += (s[i] == 'N')*1 + (s[i] == 'S')*(-1)
		x += (s[i] == 'E')*1 + (s[i] == 'W')*(-1)
		
		if (a+x, b+y) in d:
			ans += 1
		else:
			ans += 5
			d[a+x, b+y] = 1
		#print(d)
	cout(str(ans) + '\n')
	
	
	
	
	'''
	dict = {'N': 0, 'S': 1, 'W': 2, 'E': 3}
	#print(dict)
	move = [0]*4
	move[dict[s[0]]] = 1
	#print(move)
	time = 5
	
	for i in range(1, len(s)):
		if s[i] == 'N':
			time += (move[1]>0)*1 + (move[1]==0)*5
			move[1] = (move[1]>0)*(move[1]-1)
			move[2] = move[3] = 0
			move[0] += 1
		elif s[i] == 'S':
			time += (move[0]>0)*1 + (move[0]==0)*5
			move[0] = (move[0]>0)*(move[0]-1)
			move[2] = move[3] = 0
			move[1] += 1
		elif s[i] == 'W':
			time += (move[3]>0)*1 + (move[3]==0)*5
			move[3] = (move[3]>0)*(move[3]-1)
			move[0] = move[1] = 0
			move[2] += 1
		else:
			time += (move[2]>0)*1 + (move[2]==0)*5
			move[2] = (move[2]>0)*(move[2]-1)
			move[0] = move[1] = 0
			move[3] += 1
		print(move)
	cout(str(time) + '\n')
	
	'''