E. A Floor of Many Doors
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Ha HAHa haHA! You are the Mysterious Criminal Absconder, cunning trickster and nemesis of the Academy of Covert Missions.

Currently, you are on the top floor of their headquarters. HAHAHAh haha HAHH! (That's your "I'm hiding in my enemy's HQ" cackle.) In your hands is the top floor's floor plan in the form of a $$$r \times c$$$ grid. Each cell is a $$$1 \times 1$$$ square meter of space that is either a wall, a door, or an empty space.

You want to plant a bomb on this floor, and are planning to trigger it once someone enters the floor from downstairs. You've hacked the security system such that at most $$$k$$$ doors are allowed to be open at once. Once the agent arrives, all doors will be shut. From their current cell, they are only able to 1) walk to an adjacent cell that is either an empty space or an open door, or 2) open or close a door which is at a adjacent cell, both of which will take $$$1$$$ second each time they choose to do it. Of course, the agent will not be able to step on any space outside the floor plan's grid; they would fall out of the building.

Now, you've always loved playing games with this organization. To keep the game fair, you're going to have to plan this carefully in order to give them a chance to defuse this bomb. You must select 1) the cell where the agent will enter the floor and 2) the cell where the bomb will be, and determine if it is possible for them to reach the bomb. If it is, they must do so in the minimum time possible, else they will say goodbye to many precious files in their building.

Given the floor plan and the planned locations the two empty cells containing the agent's entrance and the bomb, would it be possible for the agent to defuse the bomb? If yes, what would be the minimum time for them to arrive at the cell containing the bomb?

Note: Two cells are considered adjacent if they share a common side.

Input

The first line of input contains $$$t$$$, the number of test cases.

The first line of each test case contains three space-separated integers $$$r$$$, $$$c$$$ and $$$k$$$. The $$$i$$$th of the next $$$r$$$ lines contains a string of length $$$c$$$ denoting the $$$i$$$th row. It consists of the following characters:

  • '.' denoting an empty cell;
  • '#' denoting a wall cell;
  • 'D' denoting a cell containing a door;
  • 'A' denoting an empty cell denoting the agent's entrance;
  • 'B' denoting an empty cell containing the bomb.

Constraints

  • $$$1 \le t \le 10^5$$$
  • $$$1 \le r, c, rc \le 5000$$$
  • $$$1 \le k \le 50$$$
  • The sum of $$$rc$$$ in a single file is at most $$$3\cdot 10^5$$$.
  • There is exactly one A in the grid.
  • There is exactly one B in the grid.
Output

For each test case, output a single line containing:

  • an integer denoting the minimum time for them to arrive at the cell containing the bomb; or
  • the string "HAHAHUHU" (without the quotes) if it is impossible for the agent to defuse the bomb.
Example
Input
2
3 12 3
....D...#.#B
A#.D.D..#.#.
.D..D...D.D.
7 11 8
......#....
......#..B.
##....#....
..#....####
...#...D...
...D...D...
...#...#.A.
Output
19
HAHAHUHU