Pogo (Large)

포고 스틱을 타고 평면 위를 뛰어다닌다. 점프 거리는 계속 늘어나서 첫 번째 점프는 1만큼, 두 번째 점프는 2만큼, $i$번째 점프는 정확히 $i$만큼 이동한다. 방향은 북(y 증가), 남(y 감소), 동(x 증가), 서(x 감소) 네 가지 중 하나를 고른다.

무한히 넓은 평면의 $(0, 0)$에서 출발해 $(X, Y)$에 정확히 서려고 한다. 점프를 건너뛰거나 거리를 바꿀 수 없으므로 $m$번 점프하면 사용한 거리는 순서대로 $1, 2, \dots, m$이다. 점프 횟수를 최소로 하여 $(X, Y)$에 도달하는 방법을 구하라.

첫 줄에 테스트 케이스 수 $T$가 주어진다. 이어지는 $T$개의 줄에 도착 좌표 $X$와 $Y$가 공백 하나로 구분되어 주어진다.

• $1 \le T \le 100$
• $0 \le |X|, |Y| \le 10^6$
• $(X, Y)$는 $(0, 0)$이 아니다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄씩 출력한다. x는 1부터 시작하는 테스트 케이스 번호이고, y는 N, S, E, W로 이루어진 문자열로 $i$번째 문자가 $i$번째 점프의 방향이다. 예를 들어 NSEW는 북, 남, 동, 서 순서로 뛴다는 뜻이다.

문자열은 정확히 $(X, Y)$에서 끝나야 하고, 길이가 최소여야 한다.

길이가 최소인 문자열이 여럿이면 그중 하나만 정답으로 인정한다. 문자열을 뒤에서부터 읽어 가장 작은 것을 고른다. 즉 마지막 문자를 알파벳 순서 E < N < S < W로 비교하고, 같으면 뒤에서 두 번째 문자를 비교하고, 그다음에는 뒤에서 세 번째 문자를 비교하는 식이다. 이렇게 정해진 문자열 하나를 출력한다.

$(3, 4)$에 도달하는 가장 짧은 문자열의 길이는 5이다.