Expogo

당신은 방금 최고의 선물인 Expogo 스틱을 받았다. 그 위에 올라서서 점점 더 큰 점프를 할 수 있다.

현재 무한히 넓은 이차원 뒷마당의 점 (0, 0)에 서 있으며, 가능한 한 적은 횟수로 점프하여 정수 좌표를 갖는 목표점 (X, Y)에 도달하려 한다. 목표점에 정확히 착지해야 하며, 점프하면서 그 위를 지나가는 것만으로는 충분하지 않다.

Expogo 스틱을 사용해 점프할 때마다 북쪽, 남쪽, 동쪽, 서쪽 중 하나의 기본 방위를 선택한다. Expogo 스틱을 이용한 i번째 점프에서는 선택한 방향으로 2^{(i-1)} 단위만큼 이동한다. 따라서 첫 점프에서는 1 단위, 두 번째 점프에서는 2 단위, 세 번째 점프에서는 4 단위만큼 이동하며, 이후에도 같은 방식으로 계속된다.

목표점 (X, Y)가 주어질 때 그곳에 도달할 수 있는지 판별하고, 가능하다면 가능한 한 적은 횟수로 점프하여 도달하는 방법을 제시한다.

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1GB. (X, Y) ≠ (0, 0).

테스트 세트 1 (결과 공개)

1 ≤ T ≤ 80. -4 ≤ X ≤ 4. -4 ≤ Y ≤ 4.

테스트 세트 2 (결과 공개)

1 ≤ T ≤ 100. -100 ≤ X ≤ 100. -100 ≤ Y ≤ 100.

테스트 세트 3 (결과 공개)

1 ≤ T ≤ 100. -$10^{9}$ ≤ X ≤ $10^{9}$. -$10^{9}$ ≤ Y ≤ $10^{9}$.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 목표점의 좌표를 나타내는 두 정수 X와 Y가 적힌 한 줄로 이루어진다.

각 테스트 케이스마다 Case #x: y를 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며, 번호는 1부터 시작한다. 목표점에 도달할 수 없다면 y는 IMPOSSIBLE이다. 그렇지 않다면 y는 하나 이상의 문자로 이루어진 문자열이어야 하며, 각 문자는 N(북쪽), S(남쪽), E(동쪽), W(서쪽) 중 하나로, 수행할 점프의 방향을 순서대로 나타낸다. 이 점프 순서는 마지막 점프가 끝났을 때 목표점에 도달해야 하며, 가능한 한 짧아야 한다.

예제 케이스 #1에서는 (0, 0)에서 남쪽으로 점프하여 (0, -1)로 간 다음, 동쪽으로 점프하여 (2, -1)로 가고, 이어서 북쪽으로 점프하여 (2, 3)로 갈 수 있다.

목표점에 도달하려면 적어도 2 + 3 = 5 단위의 거리가 필요하지만 처음 두 점프를 합쳐도 3 단위의 거리만 이동할 수 있으므로, 이보다 효율적인 해법, 즉 두 번 이하로 이동하는 해법은 없다고 확신할 수 있다.

예제 케이스 #2는 예제 케이스 #1를 두 축 모두에 대해 대칭 이동한 것과 같으므로, 답은 예제 케이스 #1의 답에 있는 모든 방향을 대칭으로 바꾸면 얻을 수 있다.

예제 케이스 #3에서는 EWE가 목표점에 도달하기는 하지만, 더 적은 횟수로 점프하여 도달하는 방법이 있으므로 올바른 답이 아님에 유의한다.

예제 케이스 #4에서 목표점에 도달하는 것이 불가능한 이유는 직접 알아내 보자.