Pogo (Large)

You ride a pogo stick across a plane, and its jumps keep growing. The first jump moves you 1 unit, the second jump moves you 2 units, and jump number $i$ moves you exactly $i$ units. Each jump goes in one of four directions: north (y increases), south (y decreases), east (x increases), west (x decreases).

You start at $(0, 0)$ on an infinite plane and want to stand exactly on $(X, Y)$. You cannot skip a jump or change its length, so after $m$ jumps the lengths you have used are $1, 2, \dots, m$ in that order. Reach $(X, Y)$ with as few jumps as possible.

The first line has the number of test cases $T$. Each of the next $T$ lines has the target coordinates $X$ and $Y$, separated by one space.

• $1 \le T \le 100$
• $0 \le |X|, |Y| \le 10^6$
• $(X, Y)$ is never $(0, 0)$.

For each test case print one line in the form Case #x: y. Here x is the case number starting from 1, and y is a string of the letters N, S, E, W whose $i$-th character is the direction of the $i$-th jump. For example, NSEW means north, then south, then east, then west.

The string must end exactly on $(X, Y)$, and its length must be the smallest possible.

When several strings of that smallest length work, only one of them counts as the answer. Read the strings backwards and take the smallest one: compare the last characters in the alphabetical order E < N < S < W, and if they are equal compare the second to last characters, then the third to last characters, and so on. Print that one string.

The shortest strings that reach $(3, 4)$ have length 5.