Description

Your goal is to find the minimum number of steps to eat all the dots inside an enclosed maze without ghosts.

 

The possible tiles are listed as follows:

'o': The PacMan on a tile

' ': Nothing on a tile

'.': A dot on a tile

'#': Wall

 

Your program only needs to deal with valid inputs. It is guaranteed that:​

• all tiles other than wall tiles are within an enclosed area formed by wall tiles;
• no more than 5 dots;
• there is at least one solution.

 

Example 1:

Input:

1
4 9
#########
#   o...#
# . #####
#########

 

Output:

9

Sequence of steps:

ASAWDDDDD

where:

• W: move the PacMan up
• A: move the PacMan left
• S: move the PacMan down
• D: move the PacMan right

Input

The first line contains a single integer T (1 ≤ T ≤ 100). Then T test cases follow.

For each test case:

• the first line gives two integers N and M (1 ≤ N*M ≤ 256);
• each of the next N lines consists of M characters, representing the tiles of each row.

Output

For each test, output the minimum number of steps to eat all the dots inside the enclosed maze without ghosts.

Sample Input  Download

Sample Output  Download

Tags

Discuss