## SPIRAL2 - SPIRAL RUN

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

**85236561**

**801803**

**85236561 **

**Sample 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 |