Patrick's Parabox

Patrick's Parabox is a Sokoban-like game. A Sokoban puzzle is a grid, and each cell is a wall or a floor. Several boxes and a player occupy distinct floor cells. They cannot move into wall cells or occupy the same cell. The player moves in one of four directions: left, right, up, or down. When the player touches a box, the player can push it. The goal is to move every box onto its target cell.

Read the following rules carefully. They may differ from the usual rules.

In this problem, there is only one box, and the box is the grid itself. If the player moves out of the grid, the player may be "teleported" to a cell adjacent to the box. If the player moves into the box, the player may be "teleported" to a cell on the boundary of the grid. The player also has a target cell, and the player must reach it at the end.

Given a puzzle, find the minimum number of pushes needed for the box and the player to reach their respective target cells.

The following are the detailed and formal rules.

Consider an $n\times m$ grid. Denote $(i,j)$ as the cell in row $i$ and column $j$. Rows are numbered $1, 2, \ldots, n$ from top to bottom, and columns are numbered $1, 2, \ldots, m$ from left to right.

Denote W, S, A, and D as the control commands, which move up, down, left, and right respectively.

Define $v\_\text{W}=(-1,0)$, $v\_\text{S}=(1,0)$, $v\_\text{A}=(0,-1)$, and $v\_\text{D}=(0,1)$.

Define $w\_\text{W}=(n,\left\lceil\dfrac m2\right\rceil)$, $w\_\text{S}=(1,\left\lceil\dfrac m2\right\rceil)$, $w\_\text{A}=(\left\lceil \dfrac n2\right\rceil,m)$, and $w\_\text{D}=(\left\lceil \dfrac n2\right\rceil,1)$.

In each operation, choose one control command $c$ from W, S, A, and D. Let $p$ be the cell containing the player and $b$ the cell containing the box before the operation.

• If $p+v\_c=b$ and $b+v\_c$ is a floor cell, the player moves to $p+v\_c$ and the box moves to $b+v\_c$. Only this case counts toward the answer, so it must happen as few times as possible.
• If $p+v\_c$ is a wall cell, nothing happens.
• If $p+v\_c$ is a floor cell and $p+v\_c\ne b$, the player moves to $p+v\_c$.
• If $p+v\_c=b$ and $b+v\_c$ is outside the grid, nothing happens.
• If $p+v\_c=b$, $b+v\_c$ is a wall cell, and $w\_c$ is a wall cell, nothing happens.
• If $p+v\_c=b$, $b+v\_c$ is a wall cell, and $w\_c$ is a floor cell, the player moves to $w\_c$.
• If $p+v\_c$ is outside the grid and $b+v\_c$ is a wall cell, nothing happens.
• If $p+v\_c$ is outside the grid and $b+v\_c$ is outside the grid, nothing happens.
• If $p+v\_c$ is outside the grid and $b+v\_c$ is a floor cell, the player moves to $b+v\_c$.

The list covers every possible case. Only four of those cases are valid moves, and all others leave the state unchanged.

The first line contains an integer $T$ ($1\le T\le 10^5$), the number of test cases.

Each test case is given as follows.

The first line contains two integers $n$ and $m$ ($2 \le n, m \le 10^5$), the size of the parabox.

Each of the next $n$ lines contains a string of length $m$. Each character is one of "#", ".", "p", "b", "=", or "-". Here "#" is a wall cell, "p" is the floor cell with the player, "b" is the floor cell with the box, "=" is the player's target floor cell, "-" is the box's target floor cell, and "." is any other floor cell.

Each of "p", "b", "=", and "-" appears exactly once.

The sum of $n \cdot m$ over all test cases does not exceed $4 \cdot 10^5$.

For each test case, print -1 if the box and the player cannot reach their respective target cells. Otherwise, print the minimum number of pushes on one line.

The three puzzles in the first example are real levels from the game.