Description

今天将是你终于能和猫咪 Peppurr 合影的日子！

Peppurr 即将在你的城市巡游。这座城市有无限多条南北走向和东西走向的无限长街道。任意两条垂直街道的交点称为十字路口。从任意一个十字路口出发，往四个方向（北、东、南、西）最近的十字路口都恰好相隔一个街区。

你已知 Peppurr 巡游的完整路径。你的目标是在 Peppurr 到达某个巡游路线的十字路口的同时，你也到达该路口，并且希望尽可能快地完成这件事。这就是你与 Peppurr 合影的方式！

Peppurr 的巡游起点位于你当前位置以东 $\mathbf{X}$ 个街区、以北 $\mathbf{Y}$ 个街区的十字路口。你和 Peppurr 每走完一个完整街区都需要恰好一分钟，且每分钟结束时必须到达一个十字路口；你们都不能走部分街区。

Peppurr 沿着预定路径移动。每分钟，你可以选择静止不动，或者选择向四个方向之一（北、东、南、西）移动一个街区。你和 Peppurr 都只沿街道行走。

如果你和 Peppurr 同时到达同一个十字路口，你就能成功合影（包括巡游的最后一个路口）。但 Peppurr 在巡游结束后不再接受合影，因此即使只晚一分钟到达巡游终点，也无法合影。

你有可能和 Peppurr 合影吗？如果可能，最快需要多少分钟？

Input Format

输入的第一行包含测试用例数量 $\mathbf{T}$。随后是 $\mathbf{T}$ 个测试用例，每个用例占一行，包含两个整数 $\mathbf{X}$、$\mathbf{Y}$ 和一个字符串 $\mathbf{M}$。表示 Peppurr 的巡游起点位于你当前位置以东 $\mathbf{X}$ 个街区、以北 $\mathbf{Y}$ 个街区的十字路口。字符串 $\mathbf{M}$ 是 Peppurr 的移动序列，其中第 $i$ 个字符为 $\mathbf{N}$（北）、$\mathbf{E}$（东）、$\mathbf{S}$（南）或 $\mathbf{W}$（西），对应巡游第 $i$ 分钟 Peppurr 移动的方向。

Output Format

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始）。如果无法与 Peppurr 合影，$y$ 为 IMPOSSIBLE；否则 $y$ 为从巡游开始到成功合影所需的最少分钟数。

5
4 4 SSSS
3 0 SNSS
2 10 NSNNSN
0 1 S
2 7 SSSSSSSS

Case #1: 4
Case #2: IMPOSSIBLE
Case #3: IMPOSSIBLE
Case #4: 1
Case #5: 5

Hint

样例解释

在样例 #1 中，你可以向东走 4 个街区，在巡游的最后一个十字路口与 Peppurr 合影。

在样例 #2 中，巡游起点位于你以东 3 个街区。无论如何移动，你都无法与 Peppurr 合影。

在样例 #3 中，巡游路线距离你太远，无法在巡游结束前合影。

在样例 #4 中，Peppurr 会在 1 分钟后到达你的位置，因此你甚至不需要移动！注意只能在十字路口合影，如果你向北移动而 Peppurr 向南移动，虽然会在非路口处相遇，但无法在 0.5 分钟时合影。

在样例 #5 中，你可以先向北走 2 次，再向东走 2 次，然后静止不动，下一分钟即可合影。其他路径也可能在 5 分钟时合影，但无法更快。

以下两个样例不会出现在测试集 1 或 2 中，但可能出现在测试集 3：

2
3 2 SSSW
4 0 NESW

正确输出应为：

Case #1: 4
Case #2: 4

注意在样例 #1 中，你可以在起点以南 1 个街区、以东 2 个街区的十字路口与 Peppurr 合影。在样例 #2 中，Peppurr 沿小正方形移动，当其返回起点时即可合影。

数据范围

• $1 \leqslant \mathbf{T} \leqslant 100$。
• $(\mathbf{X}, \mathbf{Y}) \neq (0, 0)$（巡游起点与你不在同一路口）。

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

• $0 \leqslant \mathbf{X} \leqslant 10$。
• $0 \leqslant \mathbf{Y} \leqslant 10$。
• $1 \leqslant \mathbf{M} \text{ 的长度} \leqslant 8$。
• $\mathbf{M}$ 仅包含 $\mathbf{N}$ 或 $\mathbf{S}$。

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

• $0 \leqslant \mathbf{X} \leqslant 1000$。
• $0 \leqslant \mathbf{Y} \leqslant 1000$。
• $1 \leqslant \mathbf{M} \text{ 的长度} \leqslant 1000$。
• $\mathbf{M}$ 仅包含 $\mathbf{N}$ 或 $\mathbf{S}$。

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

• $0 \leqslant \mathbf{X} \leqslant 1000$。
• $0 \leqslant \mathbf{Y} \leqslant 1000$。
• $1 \leqslant \mathbf{M} \text{ 的长度} \leqslant 1000$。
• $\mathbf{M}$ 可包含 $\mathbf{N}$、$\mathbf{E}$、$\mathbf{S}$ 或 $\mathbf{W}$。

翻译由 DeepSeek V3 完成