Balin is stuck in a labyrinth beneath the lonely mountain and roof is about to collapse. Add a fire breathing dragon to the mix and it’s safe to say that he is desperate to get out of there as quickly as possible. Your task is to help him find the path to get out this pickle!

The labyrinth is represented as a m-by-n matrix with Balin’s position marked as ‘s’ and the exit marked as ‘f’. Cells are marked either as ‘b’ or ‘w’. The ‘w’ marked cells represent traps in the labyrinth, designed to kill and so Balin cannot choose those cells in his path to get out. The only safe positions are the ones that are marked with b’s. Your program must output the matrix containing ‘b’ in each cell on the required path and ‘-‘ (ASCII Code 45) in the other cells. In case there is no way for Balin to survive, output “The path doesn’t exist.”.

There is only one path to come out of the labyrinth but the labyrinth contains false paths which Balin must avoid because they will eventually lead to a trap.

Input

The first line of the input will consist of an integer t representing the number of testcases.

Every testcase consists of the following lines:

The first line contains two integers n and m representing the number of rows and columns respectively.
Next n lines contain m letters denoting the map of the labyrinth.

Output

For each testcase output an n X m matrix that has ‘s’, ‘f’ at the same positions as in the input matrix and a path represented by b’s which is path from s to f and for all other positions output a ‘–‘.

If no such path exists, output "The path doesn't exist." (quotes only for clarity).

NOTE: Balin cannot move diagonally

Constraints

1

2

Example

Input: 2 6 5 bbbbw bwwfw bbbww bwwww bbbbw wwwbs 4 4 bbbw wwfw bwww bbbs Output:

bbbb- b--f- b---- b---- bbbb- ---bs The path doesn't exist.