多灾多难的公主又被大魔王抓走啦！国王派遣了第一勇士去拯救她。
身为超级厉害的术士，同时也是第一勇士的好伙伴，你决定祝他一臂之力。你为第一勇士提供了一张大魔王根据地的地图，上面标记了第一勇士和公主所在的位置，以及一些不能够踏入的禁区。你还贴心地为第一勇士制造了一些传送门，通过一个传送门可以瞬间转移到任意一个传送门，当然第一勇士也可以选择不通过传送门瞬移。传送门的位置也被标记在了地图上。此外，你还查探到公主所在的地方被设下了结界，需要集齐 $K\ (0≤K≤5)$ 种宝石才能打开。当然，你在地图上也标记出了不同宝石所在的位置。
你希望第一勇士能够带着公主早日凯旋。于是在第一勇士出发之前，你还需要为第一勇士计算出他最快救出公主的时间。
地图用一个 $R \times C$ 的字符矩阵来表示。字符 $S$ 表示第一勇士所在的位置，字符 $E$ 表示公主所在的位置，字符 $\text{#}$ 表示不能踏入的禁区，字符 $\text{\$}$ 表示传送门，字符 $\text{.}$ 表示该位置安全，数字字符 $0$ 至 $4$ 表示了宝石的类型。
第一勇士每次可以从当前的位置走到他上下左右四个方向上的任意一个位置，但不能走出地图边界。
第一勇士每走一步需要花费 $1$ 个单位时间，从一个传送门到达另一个传送门不需要花费时间。当第一勇士走到宝石所在的位置时，就视为得到了该宝石，不需要花费额外时间。

第一行是一个正整数 $T\ (1 \le T \le 10)$，表示一共有 $T$ 组数据。
每一组数据的第一行包含了三个用空格分开的正整数 $R,\ C\ (2≤R,C≤200)$ 和 $K$，表示地图是一个 $R \times C$ 的矩阵，而第一勇士需要集齐 $K$ 种宝石才能够打开拘禁公主的结界。
接下来的 $R$ 行描述了地图的具体内容，每一行包含了 $C$ 个字符。字符含义如题目描述中所述。
保证有且仅有一个 $S$ 和 $E$。$\text{\$}$ 的数量不超过 $10$ 个。宝石的类型在数字 $0$ 至 $4$ 范围内，即不会超过 $5$ 种宝石。

对于每一组数据，输出第一勇士救出公主所花费的最少单位时间。
若第一勇士无法救出公主，则输出 "oop!"（只输出引号里面的内容，不输出引号）。
每组数据的输出结果占一行。