Description

在一个n*m的有起点和终点的二维地图中找出起点终点的最短路
‘#’、’.’、‘S’、'G’分别表示墙壁、通道、起点、终点
保证输入合法，且结果不超过int范围, 地图中一点只与上下左右4个点相邻。

Input

输入的第一行是一个int型整数T，表示一个有T组数据。
每组数据第一行包含两个数n<=100，m<=100 表示二维地图的行数，列数。
接下来有n行，表示地图。

Output

输出T行，每行一个整数，表示求得的结果。如果起点终点连通，输出exist!，否则，输出not exist!.

Sample Input

2
10 10
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
10 10
#S######.#
#.#...####
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#

Sample Output

exist!
not exist!