Expogo

You have just received the best gift ever: an Expogo stick. You can stand on it and use it to make increasingly large jumps.

You are standing at point $(0, 0)$ in an infinite two-dimensional backyard. You want to reach a goal point $(X, Y)$, with integer coordinates, in as few jumps as possible. You must land exactly on the goal point. Passing over it during a jump is not enough.

Each jump, you pick a direction: north, south, east, or west. The $i$-th jump moves you $2(i-1)$ units in the chosen direction. The first jump moves 1 unit, the second moves 2 units, the third moves 4 units, and so on.

Determine whether the goal point can be reached. If it can, show how to reach it using as few jumps as possible.

The first line contains the number of test cases $T$. Each of the next $T$ lines contains two integers $X$ and $Y$, the coordinates of the goal point.

For each test case, output one line Case #x: y, where $x$ is the test case number starting from 1. If the goal point cannot be reached, $y$ is IMPOSSIBLE. Otherwise, $y$ is a string of one or more characters from N, S, E, and W, giving the directions of the jumps in order. The jumps must land exactly on the goal point after the last jump, and the string must be as short as possible.

$(X, Y) \neq (0, 0)$.

In Sample 1, you can jump south from $(0, 0)$ to $(0, -1)$, then east to $(2, -1)$, then north to $(2, 3)$. Two jumps or fewer are not enough. The goal is at least $2 + 3 = 5$ units away, but the first two jumps together cover only $1 + 2 = 3$ units.

Sample 2 is Sample 1 reflected across both axes, so its answer comes from reversing every direction in the answer to Sample 1.

In Sample 3, EWE reaches the target but is not a valid answer, because a shorter route exists.

Figure out why the target in Sample 4 cannot be reached.