题目描述

$\texttt{Patrick's Parabox}$ 是一个经典的游戏。有一个 $n\times m$ 的棋盘，格子要么是平地，要么是障碍。有一个箱子被放在一个平地上，另一个平地上站着玩家。玩家可以往上下左右四个方向走，如果是顶着箱子走，并且箱子后面是平地，那么箱子就会被推进一格。玩家的目标是把箱子推到箱子的目标位置，然后走到玩家的目标位置。

但是，本题中的推箱子游戏和一般的推箱子游戏规则不同，请仔细阅读一下规则：

本题中只有一个箱子，并且这个箱子是个“虫洞”，这意味着，如果玩家移动出了棋盘的范围，它可能会被传送到箱子边界上的一格中；如果玩家移动向箱子且这个方向上箱子无法被推动，那么玩家可能被传送到一个网格边界上的空地上。

并且玩家不止需要完成“箱子到位、玩家到位”这两个目标，还需要最小化推动箱子的次数，来节约体力。

以下是这个游戏的完整规则，请务必完整准确阅读：

给定一个 $n\times m$ 的棋盘，向量 $(i,j)$ 表示第 $i$ 行第 $j$ 列。行号为 $1\sim n$ ，列号为 $1\sim m$ 。

规定 $\texttt{WSAD}$ 分别表示玩家的四种操作（上下左右），形式化地：

$$\vec{v_W}=(-1,0),\vec{v_S}=(1,0),\vec{v_A}=(0,-1),\vec{v_D}=(0,1) $$

为了以下描述的方便，再给定四个格子：

$$\vec{w_W}=\left(n,\left\lceil\frac m2\right\rceil\right), \vec{w_S}=\left(1,\left\lceil\frac m2\right\rceil\right), \vec{w_A}=\left(\left\lceil\frac n2\right\rceil,m\right), \vec{w_D}=\left(\left\lceil\frac n2\right\rceil,1\right) $$

每一步，玩家可以选择一个方向 $\texttt\{c = W/S/A/D\}$ ，玩家当前位置矢量为 $\vec\{p\}$ ，方向为 $c$ ， $\vec\{b\}$ 是操作前包含箱子的位置矢量，那么：

• 若 $\vec\{p\}+\vec\{v_c\}=\vec\{b\}$ ，并且 $\vec\{b\}+\vec\{v_c\}$ 是平地，那么玩家移动到 $\vec\{p\}+\vec\{v_c\}$ ，箱子移动到 $\vec\{b\}+\vec\{v_c\}$ 。注意，** 只有这种情况会花费体力 ** ，你只需要最小化这种情况出现的次数。
• 若 $\vec\{p\}+\vec\{v_c\}$ 是障碍，那么什么都不发生。
• 若 $\vec\{p\}+\vec\{v_c\}$ 是平地且 $\vec\{p\}+\vec\{v_c\}\not=\vec\{b\}$ ，那么玩家移动到 $\vec\{p\}+\vec\{v_c\}$ 。
• 若 $\vec\{p\}+\vec\{v_c\}=\vec\{b\}$ 且 $\vec\{b\}+\vec\{v_c\}$ 在棋盘外，那么什么都不发生。
• 若 $\vec\{p\}+\vec\{v_c\}=\vec\{b\}$ 且 $\vec\{b\}+\vec\{v_c\}$ 是障碍， $\vec\{w_c\}$ 为障碍，那么什么都不发生。
• 若 $\vec\{p\}+\vec\{v_c\}=\vec\{b\}$ 且 $\vec\{b\}+\vec\{v_c\}$ 是障碍， $\vec\{w_c\}$ 为平地，那么玩家移动到 $\vec\{w_c\}$ 。
• 若 $\vec\{p\}+\vec\{v_c\}$ 在棋盘外且 $\vec\{b\}+\vec\{v_c\}$ 是障碍，那么什么都不发生。
• 若 $\vec\{p\}+\vec\{v_c\}$ 在棋盘外且 $\vec\{b\}+\vec\{v_c\}$ 在棋盘外，那么什么都不发生。
• 若 $\vec\{p\}+\vec\{v_c\}$ 在棋盘外且 $\vec\{b\}+\vec\{v_c\}$ 是空地，那么玩家移动到 $\vec\{b\}+\vec\{v_c\}$ 。

请注意上面枚举了每一种情况，但是实际上会有作用的操作只有 $4$ 种。而你需要最小化的，只有第一种情况的次数。

输入格式

本题多组测试。输入的第一行包含一个整数 $T$ ，表示数据组数。对于每组数据：

第一行包括两个整数 $n,m$ 表示棋盘的大小。

接下来 $n$ 行，每行一个长度为 $m$ 的字符串，表示棋盘的状态。

• $\#$ 表示此格为障碍。
• $.$ 表示此格是平地。
• $p$ 表示此格是玩家。
• $b$ 表示此格是箱子。
• = 表示此格是玩家的目的地。
• - 表示此格是箱子的目的地。

保证 $\texttt{pb=-}$ 各出现恰好一次。

输出格式

对于每组数据：

如果不可能达成目标，输出一行一个 $-1$ ；否则，输出一行一个整数，表示推箱子的最小次数。

数据范围

对于 $10\%$ 的数据，满足没有障碍格。
另有 $10\%$ 的数据， $n\le 6$ ， $m\le 6$ ， $\sum nm\le 100$ 。
另有 $20\%$ 的数据， $\sum nm\le 5000$ 。
对于 $100\%$ 的数据，满足 $\sum nm\le 4\times 10^5$ ， $1\le n,m\le 10^5$ 。

输入样例 1

3
9 9
#########
#####..-#
#..=##.##
#.p.##.##
....##.##
#...b..##
#...##.##
#....####
####.####
9 9
#########
#.......#
#.#####.#
#.#=....#
..#....-#
###.p.#.#
#.....#b#
#.....#.#
####.####
9 9
####.####
#....####
#.####.##
#.......#
#.......#
###.#####
#=.b#..##
#-..p..##
#########

输出样例 1

7
4
19

输入样例 2

1
2 2
pb
-=

输出样例 2

-1