Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3977
Pointer

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Kevin likes to play a toy pointer. At the beginning, it points to the North. Now Kevin plays with the pointer by following a given sequence of operations. Each operation turns the pointer 90 degree in clockwise or anticlockwise direction. Your task is to output the final pointing direction of the pointer after all the operations.

Input

The first line of the input contains the number of test cases T.

For each test case, there are n lines of strings consisting of only letters 'A' and 'C' (without quotes). For each string, the letter 'A' means to turn the pointer in 90 degree anticlockwise direction, 'C' means to turn the pointer 90 degree in clockwise direction. The length of any strings will not exceed 100.

Output

For each test case, output a letter ('N' for North, 'S' for South, 'W' for West, 'E' for East) corresponding to the final pointing direction.

Sample Input

2
AC
AAAC

Sample Output

N
S

Source: ACM Collegiate Programming Contest 2017 (Hong Kong)
Submit    Status