王子做了一个噩梦，它梦见公主被困在一个n*m的格子迷宫中。更糟糕的是，这个迷宫里面还有2个会杀人的恶魔。现在王子想知道，他能否在恶魔吃掉他们之前救出公主。
所有角色在迷宫中可以向4个方向移动。每一秒钟，王子可以走3步，而公主可以走1步。恶魔每一秒钟会分化出分身占领与其曼哈顿距离不超过2的格子。

注意：新化出的分身每一秒也会自己分裂去占领格子。

每一秒钟的时候，恶魔先分裂自己占领格子，然后才是王子和公主开始行动。如果王子或者公主走到了被恶魔占领的格子，那么它们就会死掉。
当王子和公主在同一个格子的时候，王子就可以救出公主了。

第一行输入一个整数T(1 \le T \le 50)，表示测试数据的数目。
对于每一组数据，第一行输入两个整数 n, m (1 \le n, m < 800)。
接下来n行，每行m个字符描述迷宫。
‘.’表示空地，可以行走。

‘X’ 表示墙，不能走。
‘M’ 表示王子。

‘G’ 表示公主。

‘Z’ 表示恶魔。

输入保证会有一个M一个G和两个Z。

输出一个整数S，表示王子最少要经过几秒钟可以救出公主。

如果没有办法救出，输出-1。