Patrick’s Parabox 是一款类似推箱子的游戏。推箱子谜题在一个网格上进行，每个单元格要么是墙，要么是地板。网格中有若干个箱子和一个玩家，它们位于不同的地板单元格上，且不能移动到墙上或重叠。你可以控制玩家向左、右、上、下四个方向移动。当玩家接触到箱子时，可以推动箱子。目标是将所有箱子移动到指定的某些目标单元格。
请仔细阅读以下规则。它们可能与通常的规则不同。
在本题中，只有一个箱子，且箱子本身就是网格。这意味着如果玩家移出网格，他们可能会被“传送”到箱子相邻的单元格；如果玩家移动到箱子所在位置，他们可能会被“传送”到网格边界上的某个单元格。此外，玩家最终也需要移动到指定的玩家目标单元格。
给定一个谜题，你需要找到推动箱子的最小次数，使得箱子和玩家都能到达各自的目标单元格。
以下是详细且正式的规则。
考虑一个 $n \times m$ 的网格。记 $(i, j)$ 为第 $i$ 行第 $j$ 列的单元格。行号从上到下为 $1, 2, \dots, n$，列号从左到右为 $1, 2, \dots, m$。
记 W, S, A, D 为控制指令，分别表示向上、向下、向左、向右移动。 定义 $v_W = (-1, 0), v_S = (1, 0), v_A = (0, -1), v_D = (0, 1)$。 定义 $w_W = (n, \lceil \frac{m}{2} \rceil), w_S = (1, \lceil \frac{m}{2} \rceil), w_A = (\lceil \frac{n}{2} \rceil, m), w_D = (\lceil \frac{n}{2} \rceil, 1)$。
在每次操作中，你可以选择一个控制指令 $c \in \{W, S, A, D\}$。记 $p$ 为操作前玩家所在的单元格，$b$ 为操作前箱子所在的单元格：
- 如果 $p + v_c = b$ 且 $b + v_c$ 是地板单元格，玩家移动到 $p + v_c$，箱子移动到 $b + v_c$。只有这种情况计入答案，且必须以最小可能的次数完成。
- 如果 $p + v_c$ 是墙，则什么也不发生。
- 如果 $p + v_c$ 是地板单元格且 $p + v_c \neq b$，玩家移动到 $p + v_c$。
- 如果 $p + v_c = b$ 且 $b + v_c$ 在网格之外，则什么也不发生。
- 如果 $p + v_c = b$，$b + v_c$ 是墙，且 $w_c$ 是墙，则什么也不发生。
- 如果 $p + v_c = b$，$b + v_c$ 是墙，且 $w_c$ 是地板单元格，玩家移动到 $w_c$。
- 如果 $p + v_c$ 在网格之外且 $b + v_c$ 是墙，则什么也不发生。
- 如果 $p + v_c$ 在网格之外且 $b + v_c$ 在网格之外，则什么也不发生。
- 如果 $p + v_c$ 在网格之外且 $b + v_c$ 是地板单元格，玩家移动到 $b + v_c$。
注意，以上列出了所有可能性，但操作仅在其中四种情况下有效（在其他情况下，什么也不会发生）。
输入格式
输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试数据组数。
对于每组测试数据： 第一行包含两个整数 $n$ 和 $m$ ($2 \le n, m \le 10^5$)，表示网格的大小。 接下来的 $n$ 行，每行包含一个长度为 $m$ 的字符串。每个字符为 “#”、“.”、“p”、“b”、“=” 和 “-”。其中，“#” 表示墙，“p” 表示玩家所在的初始地板单元格，“b” 表示箱子所在的初始地板单元格，“=” 表示玩家的目标地板单元格，“-” 表示箱子的目标地板单元格，“.” 表示其他地板单元格。
保证 “p”、“b”、“=”、“-” 各出现且仅出现一次。 保证所有测试数据的 $n \cdot m$ 之和不超过 $4 \cdot 10^5$。
输出格式
对于每组测试数据： 如果无法将箱子和玩家移动到各自的目标单元格，输出 -1。否则，输出一个整数：推动箱子的最小次数。
样例
样例输入 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
说明
第一个样例中的三个谜题是游戏中的真实关卡。