自出题目：泉水迷宫

另外，因为我不会出数据，所以我需要找一个大大帮忙出一下数据，不水就行！如果你想帮我出，那么私聊我，特别感谢

泉水迷宫

题目背景

在 11451 年 4 月的一天，小明陷入了一个神奇的迷宫里······

附注： 题目速通通道

假的！！！

题目描述

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

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

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

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

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

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

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

输入格式

从文件 spring.in 中读入数据；本题有多组数据。

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

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

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

输出格式

输出到文件 spring.out 中。

对于每组数据，如果玩家可能顺利到达目标，就输出 possible，否则就输出 impossible，每个输出之间空一格

样例 #1

样例输入 #1

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..
###############.

样例输出 #1

possible possible possible possible impossible

提示

对于 100\% 的数据，保证 T\le5， 2 \le (N\ and\ M) \le 20。