Description

你刚刚进入了世界上最简单的迷宫。你从一个 $N \times N$ 的单位方格的西北角单元格出发，目标是到达东南角单元格。你只能进行两种类型的移动：向东移动一格，或向南移动一格。你可以进入任意单元格，但不能移动出格子外。

你本以为自己是第一个解开这个迷宫的人，但你发现了脚印。你的对手 Labyrinth Lydia 已经按照上述规则走完了迷宫！

作为一个有创意的人，你不想重复 Lydia 的任何一步。具体来说，如果她的路径包含了从某个单元格 A 移动到相邻单元格 B 的一步，你的路径中不能包含从 A 到 B 的移动（但你可以访问 A 或 B，只要不是从 A 到 B）。请你找出一条满足条件的路径。

下图中，Lydia 的路径用蓝色表示，你的一种可行路径用橙色表示：

Input Format

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据，每组包含两行。第一行包含一个整数 $N$，表示迷宫的尺寸。第二行包含一个长度为 $2N-2$ 的字符串 $P$，每个字符为大写字母 E（表示向东）或 S（表示向南），表示 Lydia 的一条合法路径。

Output Format

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是一个长度为 $2N-2$ 的字符串，每个字符为大写字母 E 或 S，表示你的一条合法路径，且不与 Lydia 的路径冲突。保证至少存在一个解。

2
2
SE
5
EESSSESE

Case #1: ES
Case #2: SEEESSES

Hint

样例解释

样例 1 中，迷宫太小，你只剩下唯一一种合法解法。

样例 2 对应上图。注意，路径可以交叉。

数据范围

• $1 \leq T \leq 100$。
• $P$ 恰好包含 $N-1$ 个 E 和 $N-1$ 个 S。

测试点 1（5 分，可见）

• $2 \leq N \leq 10$。

测试点 2（9 分，可见）

• $2 \leq N \leq 1000$。

测试点 3（10 分，隐藏）

• 最多 10 个用例满足 $2 \leq N \leq 50000$。
• 其余用例满足 $2 \leq N \leq 10000$。

由 ChatGPT 4.1 翻译