4月16日，日本熊本地区强震后，受灾严重的阿苏市一养猪场倒塌，幸运的是，猪圈里很多头猪依然坚强存活。当地15名消防员耗时一天解救围困的“猪坚强”。不过与在废墟中靠吃木炭饮雨水存活36天的中国汶川“猪坚强”相比，熊本的猪可没那么幸运，因为它们最终还是没能逃过被送往屠宰场的命运。

我们假设“猪坚强”被困在一个N*M的废墟中，其中“@”表示“猪坚强”的位置，“.”表示可以直接通过的空地，“#”表示不能拆毁的障碍物，“*”表示可以拆毁的障碍物，那么请问消防员至少要拆毁多少个障碍物，才能从废墟中救出“猪坚强”送往屠宰场？（当“猪坚强”通过空地或被拆毁的障碍物移动到废墟边缘时，视作被救出废墟）

 

Input

多组数据，第一行有一个整数T，表示有T组数据。（T<=100）

以下每组数据第一行有两个整数N和M。(1<=N,M<=100)

接着N行，每行有一个长度为M的字符串。

 

Output

一个整数，为最少拆毁的障碍物数量,如果不能逃离废墟，输出-1。

 

Sample Input

33 3####@****3 4#####@.***.*3 3.#.#@#.#.

Sample Output

10-1

Hint

搜索水题，代码不难理解，就不说了

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include