P13056 [GCJ 2020 #1B] Expogo

你刚刚收到了有史以来最棒的礼物：一根 **Expogo** 跳跃棒。你可以站在上面，用它进行越来越大的跳跃。 你目前站在无限大的二维后院中的点 $(0, 0)$ 处，并试图以尽可能少的跳跃次数到达目标点 $(\mathrm{X}, \mathrm{Y})$（坐标为整数）。你必须恰好落在目标点上，仅从上方经过是不够的。 每次使用 **Expogo** 跳跃棒跳跃时，你需要选择一个基本方向：北（north）、南（south）、东（east）或西（west）。第 $i$ 次跳跃会将你移动 $2^{(i-1)}$ 个单位，因此第一次跳跃移动 1 个单位，第二次跳跃移动 2 个单位，第三次跳跃移动 4 个单位，以此类推。 给定目标点 $(\mathrm{X}, \mathrm{Y})$，判断是否可以到达该点。如果可以，请展示如何以最少的跳跃次数实现。

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

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

**样例解释** 在样例 #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 完成