博格是来自银河系三角洲象限的一种极其强大的增强人类种族。博格集体是用来描述博格文明的群体意识的术语。每个博格个体通过一个复杂的亚空间网络与集体相连，这确保了每个成员都能得到持续的监督和指导。
你的任务是通过开发一个程序来帮助博格（没错，真的）估算在迷宫中扫描外星人以进行同化的最小成本，移动方向为北、西、东和南。棘手的是，搜索的开始是由一个超过100个个体的大组进行的。每当一个外星人被同化，或者在搜索开始时，组可能会分成两个或更多组（但他们的意识仍然是集体的）。搜索迷宫的成本定义为所有参与搜索的组共同覆盖的总距离。也就是说，如果原始组走了五步，然后分成两个组每个走三步，总距离就是11=5+3+3。
输入的第一行是一个整数，N <= 50，表示输入中的测试用例数量。每个测试用例以一行包含两个整数x, y开始，其中1 <= x,y <= 50。之后，接下来有y行，每行有x个字符。对于每个字符，空格` ''表示开放空间，井号#''表示阻挡墙，字母A''表示外星人，字母S''表示搜索的起点。迷宫的周边始终是封闭的，即没有办法从S`的坐标出去。迷宫中最多有100个外星人，且每个外星人都是可以到达的。
对于每个测试用例，输出一行，包含成功搜索迷宫而不留下任何外星人存活的最小成本
2 6 5 ##### #A#A## # # A# #S ## ##### 7 7 ##### #AAA### # A# # S ### # # #AAA### #####
8 11