本题没有可用的提交语言。

题目描述：

背景

我们的主人公吉米深深爱着克里斯汀，并且想娶她为妻。到目前为止一切都还不错，但是克里斯汀是韦雷斯先生的女儿，韦雷斯先生几乎拥有镇上所有的仓库。而且韦雷斯先生绝不会让他的女儿嫁给一个不为他工作的人。令人难过的是，如果你不知道如何在仓库里正确地推箱子，你根本就不可能为韦雷斯先生工作。所以吉米首先得通过那臭名昭著的 “韦雷斯测试”。

问题

吉米收到了一些地图，每张地图都展示了一个仓库的布局轮廓。一张地图由若干方格组成。在一个方格上可能有一堵墙，或者放着一个箱子，也可能是空的。有一个或多个方格被标记为目标方格。还有一个方格被标记为吉米的起始位置。

吉米只能朝四个方向移动：北、西、东和南。吉米只能移动到一个空方格，或者是一个放有箱子且这个箱子能够被推到吉米移动方向上的下一个方格的方格。这个下一个方格必须是空的，这意味着，由于吉米移动一格，最多只有一个箱子能恰好被移动一格。顺便说一下：有墙的方格不是空的……

每张地图的边界（地图的第一行和最后一行，以及第一列和最后一列）总是有墙。每张地图上的箱子数量总是和目标方格的数量一样多，并且总是至少有一个箱子。吉米的任务是找到把箱子推到目标方格上的最短路径，以便最终每个箱子都位于一个目标方格上。为了确定一条路径是否比另一条更短，只计算吉米的移动步数，无论他在移动过程中是否推了箱子。

对于每张地图，都保证恰好存在一个最短解决方案。

输入：

第一行包含测试用例（地图）的数量。

对于每一张地图，第一行包含该地图的行数和列数（两者都小于或等于 15），它们之间用一个空格隔开。接着是地图的布局，其中 $X$ 表示有墙的方格，$T$ 表示目标方格，$.$ 表示空方格。

在下一行给出吉米的起始位置（行和列用空格隔开），然后在再下一行给出箱子的数量。接下来的几行包含各个箱子的起始位置（每行一个箱子，行和列用空格隔开）。

行和列的编号从左上角开始，从 $0$ 开始计数。

输出：

对于每个测试用例的输出，首先是一行包含 “Scenario #i:” 的内容，其中i是测试用例的编号，从 $1$ 开始。在下一行中，按照最短可行方案打印出吉米需要做出的移动操作。吉米向北（向上）移动打印字母 $n$，向西（向左）移动打印 $w$，向东（向右）移动打印 $e$，向南（向下）移动打印 $s$ 。每个测试用例的输出后面都应该跟一个空行。

输入数据1

2
8 6
XXXXXX
X.T..X
X....X
X....X
X....X
X....X
X....X
XXXXXX
5 3
1
4 3
5 4
XXXX
X.XX
X..X
XT.X
XXXX
1 1
1
2 1

输出数据1

Scenario #1:
nnnenw

Scenario #2:
s

来源：

2002 年德国达姆施塔特工业大学编程竞赛