Shortest Route

You want to visit your friend’s house who lives at some location in an infinite grid. You are initially at the origin of the infinite grid and can move only in four directions (i.e East, West, North, South).

For Example, If you are at cell (X, Y) then you can move to East i.e at cell (X+1, Y), or West i.e at cell (X-1, Y), or North i.e at cell (X, Y+1), or South i.e at cell (X, Y-1).

Your friend gives you a string ‘STR’ of length ‘N’ that represents the route to his house from the origin. The string ‘STR’ has only four different characters, i.e ‘E’, ‘W’, ‘N’, ‘S’. which represent direction East, West, North, South, respectively.

You find out that the route given by your friend is very long, and a shorter route is also possible. Your task is to find the smallest route to reach your friend’s house. See the example for better clarity.

Note:

1. There can be more than one shortest route, you should return the one which is lexicographically smallest among them.

Example:

Consider that your friend’s house is in the cell (2, 1) in the grid. And the route given by your friend is represented by the string ‘STR’= “NNSEWEE”.

One of the smallest route to reach cell (2, 1) from origin i.e cell (0, 0) is given by string  “EEN”  i.e you start from the cell (0, 0), then move East, i.e at cell (1, 0), then again move East, i.e at cell (2, 0), and then finally move North i.e at cell (2, 1).

Note, there are some other smallest routes such as “NEE”,  “ENE” etc, but “EEN” is the lexicographically smallest among them, so you should return it.  

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases, then ‘T’ test cases follow.

The first line and only line of each test case consist of a string ‘STR’ of length ‘N’ representing the route given by your friend.

Output format :

For each test case, print a single line containing a lexicographically smallest string representing the smallest route to reach your friend’s house from the origin. 

The output of each test case will be printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 50
1 <= N <= 10 ^ 4
‘STR’ has only characters ‘E’, ‘W’, ‘N’ and ‘S’. 

Where ‘T’ is the total number of test cases, ‘N’ is the length of the given string ‘STR’

Time limit: 1 sec.