你刚刚进入了世界上最简单的迷宫。你从一个 $N \times N$ 的单位网格的西北角出发，必须到达东南角。你只有两种移动方式：向东移动一个单位，或向南移动一个单位。你可以进入任何单元格，但不能做出导致你离开网格的移动。

你很兴奋能成为世界上第一个解开这个迷宫的人，但随后你看到了脚印。你的竞争对手，迷宫莉迪亚（Labyrinth Lydia），已经按照上述同样的规则在你之前解开了迷宫！

作为一个有独创性的人，你不想重复莉迪亚的任何移动。具体来说，如果她的路径包含从某个单元格 A 到某个相邻单元格 B 的单位移动，那么你的路径就不能包含从 A 到 B 的移动。（然而，在这种情况下，你的路径访问 A 或访问 B 是可以的，只要你不从 A 走到 B 即可。）请找到这样一条路径。

在下图中，莉迪亚的路径用蓝色标出，而你的一条可能的有效路径用橙色标出：

输入格式

输入的第一行给出了测试用例的数量 $T$。接下来是 $T$ 个测试用例；每个测试用例包含两行。第一行包含一个整数 $N$，表示上述迷宫的尺寸。第二行包含一个长度为 $2N - 2$ 的字符串 $P$，其中的每个字符要么是大写字母 E（代表向东），要么是大写字母 S（代表向南），表示莉迪亚穿过迷宫的有效路径。

输出格式

对于每个测试用例，输出一行 Case #x: y，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是一个长度为 $2N - 2$ 的字符串，其中的每个字符要么是大写字母 E（代表向东），要么是大写字母 S（代表向南），表示你穿过迷宫且不与莉迪亚路径冲突的有效路径，如上所述。保证至少存在一个答案。

数据范围

$1 \le T \le 100$。 $P$ 恰好包含 $N - 1$ 个 E 字符和 $N - 1$ 个 S 字符。

子任务 1（可见）

$2 \le N \le 10$。

子任务 2（可见）

$2 \le N \le 1000$。

子任务 3（隐藏）

对于最多 10 个用例，$2 \le N \le 50000$。 对于所有其他用例，$2 \le N \le 10000$。

样例

输入 1

2
2
SE
5
EESSSESE

输出 1

Case #1: ES
Case #2: SEEESSES

说明

在样例 1 中，迷宫非常小，以至于只剩下一个有效的解决方案。

样例 2 对应于上图。请注意，路径交叉是可以接受的。