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