Shortest Route Problem Statement

You want to visit your friend’s house located at some position in an infinite grid starting from origin (0, 0). You can move in four directions: East (E), West (W), North (N), and South (S).

Your friend gives you a directional string STR representing a route to their house. You need to determine the shortest possible route, minimizing the number of steps, and return the route that is also lexicographically smallest.

Input:

The first line of the input contains an integer T, the number of test cases.
Each of the next T lines contains a string STR of length N, representing the route.

Output:

For each test case, output a single line with the shortest lexicographical route string to your friend's house.

Example:

Input:
1
NNSEWEE

Output:
EEN

Explanation: For the test case where STR = "NNSEWEE", the smallest route to reach the destination (2, 1) from origin (0, 0) is 'EEN'. This route is lexicographically smallest among other options like 'NEE', 'ENE'.

Constraints:

• 1 <= T <= 50
• 1 <= N <= 10^4
• STR contains only characters 'E', 'W', 'N', 'S'
• Time limit: 1 sec.

Note:

You do not need to print anything; the function only needs to return the final result.