Patrick's Parabox is a Sokoban-like game. A Sokoban puzzle is a gird, and each cell is a wall or a floor. There are several boxes and a player in some distinct floor cells, and they can not move to the wall cells or coincide. You can control the player to move in one of four directions, left, right, up, and down. When the player touches a box, it can push the box. The target is to move all boxes to some target cells.

Please read the following rules carefully. They may be different from the usual rules

In this problem, there is only one box, and the box is the grid itself. That means if the player moves out of the grid, it may be ``teleported'' to a cell adjacent to the box; if the player moves to the box, it may be ``teleported'' to a cell on the boundary of the grid. Besides, there is also a target cell for the player. The player needs to move to the target cell at the end too.

Given a puzzle, you need to find the minimum times to push the box, such that the box and the player move to the target cell separately.

The following are the detailed and formal rules.

Consider an  grid. Denote as the cell in -th row and -the column. The rows are numbered , , , from top to bottom, and the columns are numbered , , , from left to right.

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

Define that , , , .

Define that , , , .

In each operation, you can choose one of the control commands , one of W, S, A, and D. Denote as the cell which contains the player and as the cell which contains the box before the operation:

• If and is a floor cell, the player moves to and the box moves to . Only this case will be counted in the answer.
• If is a wall cell, nothing happens.
• If is a floor cell and , the player moves to .
• If and is outside the grid, nothing happens.
• If , is a wall cell and is a wall cell, nothing happens.
• If , is a wall cell and is a floor cell, the player moves to .
• if is outside the grid and is a wall cell, nothing happens.
• if is outside the grid and is outside the grid, nothing happens.
• if is outside the grid and is a floor cell, the player moves to .

There are multiple test cases. The first line of input contains an integer (), the number of test cases.

For each test case:

The first line contains two integers  and (, ), the size of the parabox.

Each of the following  lines contains a string of length . Each character is one of ”#”, ”.”, ”p”, ”b”, ”=” and ”-”. ”#” denotes the wall cell, ”p” denotes the floor cell which contains the player, ”b” denotes the floor cell which contains the box, ”=” denotes the target floor cell of the player, ”-” denotes the target floor cell of the box, and ”.” denotes the other floor cell.

It is guaranteed that each of ”p”, ”b”, ”=”, ”-” occurs exactly once.

It is guaranteed that the sum of  over all test cases does not exceed .

For each test case:

If it is impossible to move the box and the player to the target cells, output . Otherwise, output an integer -- the minimum times to push the box.

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

7
4
19

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

1
2 2
pb
-=

-1