传说@@F*&%(;´༎ຶД༎ຶ`)城市有无数宝藏，于是Gealo便决定去淘宝。
通过高科技Gealo将@@F*&%(;´༎ຶД༎ຶ`)城市模拟成一个2d的网格，自己的位置用’x’表示’.’正常的道路，g表示有宝藏。Gealo是一个注重效率的人于是他摆脱你们帮忙编程找到从x点出发经过所有g点回到x点所要走的最短路。（Gealo可以向8个方向走）

第一行一个t表示组数。
每组数据有两个数字n，m表示网格的长和宽(0<n,m<20)，
然后接下来的n行m列描述这个城市的大致情况。g点不超过15个。

每组数据输出一个最短距离