Bạn vừa nhận được món quà tuyệt vời nhất từ trước đến nay: một chiếc gậy Pogo. Gậy pogo là dụng cụ dùng để nhảy lên khỏi mặt đất khi bạn đang đứng trên đó.

Chiếc gậy Pogo này rất đặc biệt: cú nhảy thứ nhất sẽ đưa bạn đi một khoảng cách \(1\) đơn vị, cú nhảy thứ hai sẽ đưa bạn đi \(2\) đơn vị, cú nhảy thứ ba là \(3\) đơn vị, và cứ tiếp tục như vậy. Bạn chỉ có thể nhảy theo bốn hướng bằng chiếc gậy này: bắc (tăng \(y\)), nam (giảm \(y\)), đông (tăng \(x\)) hoặc tây (giảm \(x\)).

Bây giờ bạn muốn chơi một trò chơi trong sân sau của mình, nơi được mô hình hóa như một mặt phẳng vô hạn. Bạn đang đứng với chiếc gậy tại điểm \((0, 0)\) và bạn muốn đi đến điểm \((X, Y)\).

Điểm \((X, Y)\) sẽ không bao giờ là \((0, 0)\), và nó luôn có thể đạt được từ điểm xuất phát của bạn.

Hãy kiểm tra kỹ phần dữ liệu ra, vì yêu cầu đầu ra cho tập dữ liệu nhỏ (Small) và tập dữ liệu lớn (Large) là không giống nhau.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ thử nghiệm, \(T\). Tiếp theo là \(T\) bộ thử nghiệm, mỗi bộ trên một dòng. Mỗi dòng gồm \(2\) số nguyên cách nhau bởi một khoảng trắng, \(X\) và \(Y\), là tọa độ của điểm bạn muốn đến.

Dữ liệu ra

Với mỗi bộ thử nghiệm, hãy xuất một dòng chứa "Case #x: y", trong đó x là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và y là một chuỗi đại diện cho các hướng di chuyển. Ví dụ, nếu bạn di chuyển theo hướng bắc, sau đó nam, sau đó đông, rồi tây, chuỗi này sẽ là NSEW.

• Đối với tập dữ liệu nhỏ (Small), đầu ra được coi là đúng nếu nó không mất quá \(500\) bước nhảy để đến đích trong mỗi bộ thử nghiệm.
• Đối với tập dữ liệu lớn (Large), đầu ra được coi là đúng nếu nó đến được điểm đích với số bước nhảy ít nhất có thể.

Nếu có nhiều giải pháp đúng, hãy in ra bất kỳ giải pháp nào.

Ràng buộc

• \(1 \le T \le 50\) (Small).
• \(0 \le |X|, |Y| \le 100\) (Small).
• \(1 \le T \le 100\) (Large).
• \(0 \le |X|, |Y| \le 10^6\) (Large).

Phân nhóm

Các giới hạn của từng tập dữ liệu được nêu trong mục Ràng buộc.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

2
3 4
-3 4

Case #1: ENWSEN
Case #2: ENSWN

Nguồn

Google Code Jam 2013, Vòng 1C, bài Pogo.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.