Description

你刚刚收到了有史以来最棒的礼物：一根 Expogo 跳跃棒。你可以站在上面，用它进行越来越大的跳跃。

你目前站在无限大的二维后院中的点 $(0, 0)$ 处，并试图以尽可能少的跳跃次数到达目标点 $(\mathrm{X}, \mathrm{Y})$（坐标为整数）。你必须恰好落在目标点上，仅从上方经过是不够的。

每次使用 Expogo 跳跃棒跳跃时，你需要选择一个基本方向：北（north）、南（south）、东（east）或西（west）。第 $i$ 次跳跃会将你移动 $2^{(i-1)}$ 个单位，因此第一次跳跃移动 1 个单位，第二次跳跃移动 2 个单位，第三次跳跃移动 4 个单位，以此类推。

给定目标点 $(\mathrm{X}, \mathrm{Y})$，判断是否可以到达该点。如果可以，请展示如何以最少的跳跃次数实现。

Input Format

输入的第一行包含测试用例的数量 $\mathrm{T}$。接下来是 $\mathrm{T}$ 个测试用例，每个测试用例占一行，包含两个整数 $\mathrm{X}$ 和 $\mathrm{Y}$，表示目标点的坐标。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是 IMPOSSIBLE（如果无法到达目标点）。否则，$y$ 应为一个由若干字符组成的字符串，每个字符为 $\mathrm{N}$（北）、$\mathrm{S}$（南）、$\mathrm{E}$（东）或 $\mathrm{W}$（西），表示按顺序跳跃的方向。此跳跃序列必须在最后一次跳跃结束时到达目标点，且必须是最短的可能序列。

4
2 3
-2 -3
3 0
-1 1

Case #1: SEN
Case #2: NWS
Case #3: EE
Case #4: IMPOSSIBLE

Hint

样例解释

在样例 #1 中，你可以从 $(0, 0)$ 向南跳到 $(0, -1)$，然后向东跳到 $(2, -1)$，最后向北跳到 $(2, 3)$。

我们可以确定没有更高效的解决方案（两次或更少跳跃），因为到达目标点至少需要 $2 + 3 = 5$ 个单位的距离，而前两次跳跃总共只能提供 $3$ 个单位的距离。

注意，样例 #2 是样例 #1 关于两个坐标轴的镜像，因此答案也是样例 #1 答案中所有方向的镜像。

在样例 #3 中，注意 EWE 不是一个有效答案，尽管它能到达目标点，因为存在使用更少跳跃次数的方案。

我们留给你思考为什么在样例 #4 中无法到达目标点。

数据范围

• $(\text{X}, \text{Y}) \neq (0, 0)$。

测试集 1（5 分，可见判定）

• $1 \leqslant \text{T} \leqslant 80$。
• $-4 \leqslant \text{X} \leqslant 4$。
• $-4 \leqslant \text{Y} \leqslant 4$。

测试集 2（8 分，可见判定）

• $1 \leqslant \text{T} \leqslant 100$。
• $-100 \leqslant \text{X} \leqslant 100$。
• $-100 \leqslant \text{Y} \leqslant 100$。

测试集 3（16 分，可见判定）

• $1 \leqslant \text{T} \leqslant 100$。
• $-10^{9} \leqslant \text{X} \leqslant 10^{9}$。
• $-10^{9} \leqslant \text{Y} \leqslant 10^{9}$。

翻译由 DeepSeek V3 完成