L. Self Destructing Sokoban Swarm
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a 2D grid with obstacles, you want to move a robot to point $$$B$$$. To do this, you can summon robots at spawn points marked as $$$A$$$. (As long as it isn't obstructed)

You may also instruct robots to move. A robot can move into an adjacent cell if there is empty space in that cell. However, if there is an obstacle, the movement will be unsuccessful. If there is a robot, the robot is able to push it, as long as the cell it is pushed to is empty. If there is another robot or an obstacle, the movement is unsuccessful. The outside of the grid is made of obstacles, so robots may not move outside the grid.

After a robot is instructed to move, even if the move was unsuccessful, the robot will self destruct and cease to exist, leaving an unoccupied cell. A pushed robot does not self destruct.

Here are $$$5$$$ examples of what happens when the red robot moves to the right:

Your goal is to find the minimum number of robots you need to summon in order to move a robot to point $$$B$$$ (Moving a robot to point $$$B$$$ only for it to immediately self destruct does not count).

If it is impossible to move a robot to point $$$B$$$, print $$$-1$$$.

Additionally, it is guaranteed by the test data that if it is possible to move a robot to point $$$B$$$, it can be done so in at most $$$4 \cdot 10^{18}$$$ summoned robots.

Input

The first line contains the number of test cases $$$t$$$ $$$(1 \leq t \leq 3$$$). The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \leq n, m \leq 1000$$$).

The next $$$n$$$ lines of each test case contain $$$m$$$ characters, representing the 2D grid.

If a character on a line is '.', the corresponding cell is empty. If it is '#', the cell is an obstacle. If it is 'A', the cell is a robot spawn point. If it is 'B', the cell is the target destination of the robots.

Once again, the test data guarantees that if it is possible to move a robot to point $$$B$$$, it can be done so in at most $$$4 \cdot 10^{18}$$$ summoned robots.

—

Tests in subtasks are numbered from $$$1−20$$$ with samples skipped. Each test is worth $$$\frac{100}{20}=5$$$ points.

Test $$$1$$$ satisfies that there is exactly one 'A' cell.

Tests $$$2-3$$$ satisfy $$$n = 1$$$.

Tests $$$4-10$$$ satisfy $$$n, m \leq 50$$$.

Tests $$$11-20$$$ satisfy no additional constraints.

Output

Print one integer, the minimum number of robots you need to summon in order to move a robot to point $$$B$$$, or $$$-1$$$ if it is impossible.

Example
Input
3
3 3
AA.
AA.
##B
5 5
AA...
A.##.
.AAAA
A..##
#.B.#
6 6
AA....
AA....
......
......
......
.....B
Output
4
-1
64
Note

For the first testcase of the sample, $$$4$$$ robots are required to push one to $$$B$$$. Here is a visualization:

—

Problem Idea: Alex_C

Problem Preparation: HaccerKat

Occurrences: Novice L / Advanced H