OJ现已增加邮箱找回密码功能，还没有绑定邮箱的同学们请抓紧时间，以免密码丢失无法找回
题目描述
夜深了，史蒂夫站在森林迷宫的入口，看着地图中显示出的宝箱图标，他想是现在回家睡觉还是进入一探究竟。
看着自己带着残破不堪的铁盔甲又怕贸然进入成了怪物们的夜宵，因此他想在此缜密计算一下是否能安全进入。不过他发现一个十分重要的问题，他把他的脑子放在了床边的箱子里，所以呢现在就请你来帮帮他~
史蒂夫所处的是方块世界，因此这个迷宫可以很容易的表示为n*m的矩阵，用"."表示空地，用"#"表示不可穿过的障碍物(也不可拆除)，"S"为迷宫起点，"T"为宝箱位置(ST不会相同)。
在迷宫中由于没有阳光，如果一个方块亮度低于8个单位则这个方块可能会产生怪物，那么在史蒂夫看来这里是危险的他会不愿意进入这种方块(宝箱位置不需要照亮)。
而在迷宫的高处有着p个火把，能够提为周围供14个单位的亮度，这个亮度会按照曼哈顿距离衰减且不会被墙壁遮挡(在高处)。
现在史蒂夫告诉你他从地图上看到的地形信息和火把位置，请帮他计算他从起点到终点的最小步数(每步只能向上下左右四个方向走)，如果史蒂夫无法安全抵达宝箱位置则对他说"Good night"。
怪物生成规则、火把亮度、照亮范围如图，右下角图T表示火把数值表示亮度，同一个方块被多个火把照亮时取最大值。
看着自己带着残破不堪的铁盔甲又怕贸然进入成了怪物们的夜宵，因此他想在此缜密计算一下是否能安全进入。不过他发现一个十分重要的问题，他把他的脑子放在了床边的箱子里，所以呢现在就请你来帮帮他~
史蒂夫所处的是方块世界，因此这个迷宫可以很容易的表示为n*m的矩阵，用"."表示空地，用"#"表示不可穿过的障碍物(也不可拆除)，"S"为迷宫起点，"T"为宝箱位置(ST不会相同)。
在迷宫中由于没有阳光，如果一个方块亮度低于8个单位则这个方块可能会产生怪物，那么在史蒂夫看来这里是危险的他会不愿意进入这种方块(宝箱位置不需要照亮)。
而在迷宫的高处有着p个火把，能够提为周围供14个单位的亮度，这个亮度会按照曼哈顿距离衰减且不会被墙壁遮挡(在高处)。
现在史蒂夫告诉你他从地图上看到的地形信息和火把位置，请帮他计算他从起点到终点的最小步数(每步只能向上下左右四个方向走)，如果史蒂夫无法安全抵达宝箱位置则对他说"Good night"。
怪物生成规则、火把亮度、照亮范围如图，右下角图T表示火把数值表示亮度，同一个方块被多个火把照亮时取最大值。
输入
第一行一个整数T，表示样例组数，1 <= T <= 30。
对于每个样例
第一行两个整数n,m,p，表示矩阵大小和火把数目，2 <= n,m <= 100, 0 <= p <= 10。
接下来n行每行m个字符表示矩阵地形信息。
接着p行每行2个整数x,y，表示火把位置，1 <= x <= n, 1 <= y <= m。(左上角为(1, 1)右下角为(n, m))
对于每个样例
第一行两个整数n,m,p，表示矩阵大小和火把数目，2 <= n,m <= 100, 0 <= p <= 10。
接下来n行每行m个字符表示矩阵地形信息。
接着p行每行2个整数x,y，表示火把位置，1 <= x <= n, 1 <= y <= m。(左上角为(1, 1)右下角为(n, m))
输出
对于每个样例
如果他无法安全抵达输出"Good night"。(不包含引号)
否则输出一个整数表示最少步数。
如果他无法安全抵达输出"Good night"。(不包含引号)
否则输出一个整数表示最少步数。
样例输入 Copy
4
3 3 1
S..
...
..T
1 1
3 3 0
S..
...
..T
3 3 1
S#.
.#.
.#T
1 1
12 5 3
S....
.....
###..
.....
....T
.....
.....
.....
.....
.....
.....
.....
1 1
12 1
12 5
样例输出 Copy
4
Good night
Good night
18
提示
样例解释
样例1 全图都被照亮只向下向右即可走到。
样例2 全图都是黑暗的无法抵达。
样例3 被障碍物拦断无法抵达。
样例4 亮度和障碍物如下所示
样例1 全图都被照亮只向下向右即可走到。
样例2 全图都是黑暗的无法抵达。
样例3 被障碍物拦断无法抵达。
样例4 亮度和障碍物如下所示