Bạn vừa nhận được món quà tuyệt vời nhất từ trước đến nay: một cây gậy Expogo. Bạn có thể đứng trên nó và dùng nó để thực hiện những cú nhảy ngày càng xa.

Hiện tại, bạn đang đứng tại điểm \((0, 0)\) trong sân sau hai chiều vô hạn và muốn đến điểm đích \((X, Y)\) có tọa độ nguyên bằng ít cú nhảy nhất có thể. Bạn phải tiếp đất chính xác tại điểm đích; chỉ nhảy qua nó là chưa đủ.

Mỗi lần dùng gậy Expogo, bạn chọn một hướng chính: bắc, nam, đông hoặc tây. Cú nhảy thứ \(i\) đưa bạn đi \(2^{i-1}\) đơn vị theo hướng đã chọn; vì vậy các cú nhảy lần lượt dài \(1, 2, 4,\ldots\) đơn vị.

Cho điểm đích \((X, Y)\), hãy xác định liệu có thể đến đó hay không; nếu có, hãy chỉ ra cách thực hiện bằng ít cú nhảy nhất có thể.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Tiếp theo là \(T\) bộ test, mỗi bộ gồm một dòng chứa hai số nguyên \(X\) và \(Y\), là tọa độ điểm đích.

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ \(1\)), còn y là IMPOSSIBLE nếu không thể đến đích. Nếu có thể, y phải là chuỗi gồm một hoặc nhiều ký tự N (bắc), S (nam), E (đông) hoặc W (tây), biểu diễn theo thứ tự hướng của các cú nhảy. Chuỗi phải đưa bạn đến đích sau cú nhảy cuối và phải ngắn nhất có thể.

Ràng buộc

• \((X,Y)\ne(0,0)\).

Phân nhóm

Test Set 1 (Phán quyết hiển thị)

• \(1\le T\le80\).
• \(-4\le X\le4\).
• \(-4\le Y\le4\).

Test Set 2 (Phán quyết hiển thị)

• \(1\le T\le100\).
• \(-100\le X\le100\).
• \(-100\le Y\le100\).

Test Set 3 (Phán quyết hiển thị)

• \(1\le T\le100\).
• \(-10^9\le X\le10^9\).
• \(-10^9\le Y\le10^9\).

Đ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
-2 -3
3 0
-1 1
???+ success "Output"sample
Case #1: SEN
Case #2: NWS
Case #3: EE
Case #4: IMPOSSIBLE
```

??? "Giải thích"
    Trong trường hợp mẫu số 1, bạn có thể nhảy về nam từ $(0,0)$ đến $(0,-1)$, rồi về đông đến $(2,-1)$, rồi về bắc đến $(2,3)$.

    Không thể có lời giải hiệu quả hơn (không quá hai bước), vì cần ít nhất $2+3=5$ đơn vị khoảng cách để đến đích, còn tổng độ dài hai cú nhảy đầu chỉ là $3$.

    Trường hợp mẫu số 2 giống trường hợp mẫu số 1 nhưng phản xạ qua cả hai trục, nên đáp án thu được bằng cách phản xạ mọi hướng trong đáp án mẫu số 1.

    Trong trường hợp mẫu số 3, `EWE` không hợp lệ dù đến được đích, vì có cách dùng ít cú nhảy hơn.

    Bạn hãy tự xác định vì sao không thể đến đích trong trường hợp mẫu số 4.

Nguồn

Google Code Jam 2020, Vòng 1B, bài Expogo.

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