Spring & Maze $\gets$ 链接，欢迎 AC

题目描述

一个迷宫的地图可以看作是一个 $N$ 行 $M$ 列的字符矩阵，矩阵的每个元素可能是：

1. .，表示空地，玩家可以自由走到这一位置；

2. # ，表示障碍，玩家不能走到这一位置；

3. $1 - 9$ 的数字，表示这一位置中有一只攻击力为相应数字的怪兽，玩家如果走到这一位置将损失相应数值的血量，如果血量小于等于 $0$，游戏就将以玩家失败结束；

4. 字符 $S$，表示这一位置有神奇泉水，玩家走到这一位置血量将恢复为 $10$。

游戏开始时，玩家处于第一行第一列，血量为 $10$，玩家每步可以走到上下左右相邻的格子，但不能走出地图，玩家目标是走到地图的第 $N$ 行第 $M$ 列，

你的任务很简单，请判断玩家是否有可能达到这一目标。

注意，游戏允许玩家重复经过某个位置，而且如果重复经过的位置中有怪兽或泉水，那么每经过一次，相应的作用就会生效一次。

输入格式

本题有多组数据。

输入的第一行是数据的组数 $T$。

每组数据的第一行有两个整数 $N$ 和 $M$，分别表示地图的行数和列数。

接下来的 $N$ 行，每行有 $M$ 个字符，表示游戏的地图，每个字符是 ., #, $1-9$ 的数字或者大写字母 $S$。输入保证地图的第一行第一列和第 $N$ 行第 $M$ 列一定是 .。

输出格式

对于每组数据，如果玩家可能顺利到达目标，就输出 possible，否则就输出 impossible。

每个输出之间要换行。

Single Input

5
5 5
.....
####.
.....
.####
.....
5 5
.....
####.
97...
9#2##
97...
3 11
.111111111.
.#########.
..22222....
4 9
.#222#111
4#S#2#1#S
4#3#S#1#9
S33#111#.
2 16
..111111111111..
###############.

Single Output

possible 
possible 
possible 
possible 
impossible

评测约定

本题采用捆绑测试，其中：

	Subtask 1	Subtask 2	Total
分值	$100$	$100$	$100$
评测方式	最小值	最小值	最小值
测试点	$1$	$2,\ 3,\ 4$	ALL

• 本题没有部分分。只有你通过了所有测试点，才可以得到 $100$ 分，否则你将得到 $0$ 分。

数据约定

对于 Subtask 1，保证 $T \le 10$。

对于 $100\%$ 的数据，保证 $T\le20$，$2 \le N, M \le 20$。

数据保证终点处的字符为 . 或 $S$。