패트릭의 패러박스

Patrick's Parabox는 Sokoban과 비슷한 게임이다. 소코반 퍼즐은 격자로 주어지며, 각 칸은 벽이거나 바닥이다. 여러 상자와 플레이어가 서로 다른 바닥 칸에 놓여 있으며, 이들은 벽 칸으로 이동하거나 같은 칸에 겹칠 수 없다. 플레이어는 왼쪽, 오른쪽, 위, 아래 네 방향으로 움직일 수 있다. 플레이어가 상자에 닿으면 상자를 밀 수 있다. 목표는 모든 상자를 목표 칸으로 옮기는 것이다.

아래 규칙을 주의 깊게 읽으시오. 일반적인 규칙과 다를 수 있다.

이 문제에는 상자가 하나뿐이며, 상자는 격자 그 자체이다. 플레이어가 격자 밖으로 나가면 상자에 인접한 칸으로 "순간이동"할 수 있고, 플레이어가 상자 쪽으로 이동하면 격자 가장자리의 칸으로 "순간이동"할 수 있다. 플레이어에게도 목표 칸이 있으며, 마지막에 그곳에 도달해야 한다.

주어진 퍼즐에서 상자와 플레이어가 각자의 목표 칸에 도달하기 위해 필요한 최소 밀기 횟수를 구하라.

다음은 자세하고 정식인 규칙이다.

$n\times m$ 격자를 생각하자. $(i,j)$는 $i$행 $j$열의 칸을 뜻한다. 행은 위에서 아래로 $1, 2, \ldots, n$번, 열은 왼쪽에서 오른쪽으로 $1, 2, \ldots, m$번 번호를 붙인다.

W, S, A, D는 각각 위, 아래, 왼쪽, 오른쪽으로 이동하는 명령이다.

$v\_\text{W}=(-1,0)$, $v\_\text{S}=(1,0)$, $v\_\text{A}=(0,-1)$, $v\_\text{D}=(0,1)$로 정의한다.

$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)$, $w\_\text{D}=(\left\lceil \dfrac n2\right\rceil,1)$로 정의한다.

각 연산에서는 W, S, A, D 중 하나의 명령 $c$를 고른다. 연산 전 플레이어가 있는 칸을 $p$, 상자가 있는 칸을 $b$라고 하자.

• $p+v\_c=b$이고 $b+v\_c$가 바닥 칸이면, 플레이어는 $p+v\_c$로, 상자는 $b+v\_c$로 옮겨 간다. 답에 계산되는 경우는 이 경우뿐이므로, 이 경우가 가능한 한 적게 일어나야 한다.
• $p+v\_c$가 벽 칸이면 아무 일도 일어나지 않는다.
• $p+v\_c$가 바닥 칸이고 $p+v\_c\ne 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을 출력한다. 그렇지 않으면 상자를 밀어야 하는 최소 횟수를 정수로 한 줄에 출력한다.

예제의 세 퍼즐은 게임에 실제로 등장하는 레벨이다.