Description

你刚刚收到了有史以来最棒的礼物——一根弹跳杆（Pogo stick）。弹跳杆可以让你站在上面，从地面起跳。

这根弹跳杆非常特别：第一次跳跃会让你移动 $1$ 个单位距离，第二次跳跃会移动 $2$ 个单位距离，第三次跳跃会移动 $3$ 个单位距离，依此类推。你每次只能选择四个方向中的一个跳跃：北（$y$ 增大）、南（$y$ 减小）、东（$x$ 增大）或西（$x$ 减小）。

现在你想在自家后院玩一个游戏，我们将后院抽象为无限大的平面。你一开始站在 $(0, 0)$，你想跳到 $(X, Y)$ 这个点。

点 $(X, Y)$ 保证不会是 $(0, 0)$，并且总是可以从起点到达。

请仔细阅读输出部分，因为小数据集和大数据集的输出要求并不相同。

Input Format

输入的第一行为测试用例数量 $T$。接下来有 $T$ 行，每行包含两个用空格分隔的整数 $X$ 和 $Y$，表示你要到达的目标点坐标。

Output Format

对于每个测试用例，输出一行 "Case #x: y"，其中 $x$ 为测试用例编号（从 $1$ 开始），$y$ 是一个字符串，表示每次跳跃的方向。例如，如果你依次向北、南、东、西跳跃，输出应为 NSEW。

对于小数据集，只要每个测试用例中到达终点所用跳跃次数不超过 $500$，你的输出就被认为是正确的。

对于大数据集，只有在使用最少跳跃次数到达终点时，输出才被认为是正确的。

如果存在多种正确方案，输出任意一种即可。

2
3 4
-3 4

Case #1: ENWSEN
Case #2: ENSWN

Hint

样例说明

对于第一个样例，如果这是大数据集，则该输出不被认为是正确答案，因为跳跃次数不是最少的。如果你输出 WNSEN，则对于大数据集来说是正确输出。

限制条件

小数据集（10 分，测试集 1 - 可见）

• $1 \leqslant T \leqslant 50$
• $0 \leqslant |X|, |Y| \leqslant 100$

大数据集（25 分，测试集 2 - 隐藏）

• $1 \leqslant T \leqslant 100$
• $0 \leqslant |X|, |Y| \leqslant 10^6$

翻译由 ChatGPT-4.1 完成。