SPIRAL RUN

The run starts from the center point. At each step you have to move in the spiral path as shown in the figure. At each step you can move exactly 1 unit(say 1cm). The path of the run should not overlap. Find the direction of the next move after n moves.

Input Specification:

The first line consists of an integer t, denoting the number of test cases. For the next t lines, each line consists of an integer n, the number of moves already made.

Output Specification:

For each test case find the direction of the next move after n moves.

Note: The first letter alone must be capitalized

Input Constraints:

1<=t<=100

0<=n<=50000000

Sample Input:

9

0

1

2

3

4

9

12

801803

12345678

Sample Output:

North

East

South

South

West

East

South

East

South