Problem: Problem description.
Sumit is enjoying his vacations alone in a 2D world (yes, he knows magic), until his GPS tracker stopped working. The great thing about his GPS tracker is that it sends the direction of his traveled path from the starting of his adventure to his best friend. Being his best friend, find Sumit's direction with respect to his starting position. It is sure that Sumit's final position doesn't coincides with his initial position. 

Input

First line of input will contain an integer T , implying the number of testcases in the subtask.

Following T lines will contain distinct string S containing only following letters 'N' , 'S' , 'E' and  'W' , implying the four directions. 


one of the example of the input string S is "NEWNEWS", which means that Sumit first moved one unit north and after moving one unit north he moved one unit to the east and after moving one unit to the east he moved one unit to the west ....so on and so forth....

    
Note:The directions are according to the geographical North , means if he moves EAST by one unit and after that again moves EAST by one unit, his final direction will be EAST (2 units) and  not  SOUTHEAST. 

Output

For each test case, output a single line containing the final direction of Sumit.
Output directions can be : "NORTH" , "SOUTH" , "EAST" , "WEST" , "NORTHEAST" , "NORTHWEST" , "SOUTHEAST" and "SOUTHWEST" . 

Note:Only these 8 directions should be printed(without " ") and all letters should be uppercase. 

Constraints

1 ≤ T ≤ 100
1 ≤ length of S ≤ 50


Example
Input:
3
NEW
NNSSE
NE

Output:
NORTH
EAST
NORTHEAST


Explanation
move       Direction after move
Testcase 1: 
N               NORTH
E               NORTHEAST
W              WEST  

Testcase 2: 
N               NORTH
N               NORTH(2 unit)
S               NORTH(1 unit)
S               NORTH(0 unit) , or, same as initial position.
E               EAST

Testcase 3: self-explanatory.

Solution (in PYTHON):

Solution:
for _ in range(0,input()):
    a,ns,ew=raw_input(),['SOUTH','','NORTH'],['WEST','','EAST']
    print ns[int(round((a.count('N')-a.count('S'))/abs(a.count('N')-a.count('S')+.1)))+1]+ ew[int(round((a.count('E')-a.count('W'))/abs(a.count('E')-a.count('W')+.1)))+1]