SPIRAL2 - 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

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

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

Note: The first letter alone must be capitalized

Constraints

1 <= t <= 100

0 <= n <= 50000000

Example

Input:
9
0
1
2
3
4
9
12
801803
12345678

Output:
North
East
South
South
West
East
South
East
South

Added by:cegprakash
Date:2012-05-10
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: GOSU

hide comments
2017-02-12 11:22:24
easy one AC in 1 go:-)
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.