Original problem statement (in Polish) can be found here. (It contains some more story that was removed from this version, because certain pun does not make any sense in English).

There is a grid with n rows and m columns, consisting of 1x1 squares. There is exactly one square with a laser and one (different) square with a sensor. The laser emits a beam of concentrated light from the middle of its square, in one of the four directions (north, south, east or west). Some squares are blocked, so they don't let the light through. (In that sense, square with a laser is also considered blocked).

We have a number of two-sided mirrors. We can place them on the middle of a square, in one of the two configurations (45 degrees). Mirrors placed in such a way reflect the light, making a right angle (90 degrees).

Your task is to guide the light to the sensor, using the minimum number of mirrors.

Input

The first line contains a single integer t, denoting the number of testcases. Then, testcases follow.

The description of a single testcase begins with two integers n, m (1 <= n, m <= 200) - number of rows and columns, respectively. Then, n lines follow, each containing m characters. j-th character in i-th line denotes a square in i-th row nad j-th column. "." (a dot) denotes free square, "#" denotes blocked square. There is exactly one laser on the grid, represented by one of these four characters: "<", ">", "v" or "^" (it depends on the direction of the laser). There is also exactly one sensor, represented by "C". No other characters can appear in a line.

Output

For every testcase you should print n lines with m characters, denoting the grid from the input, but with mirrors placed on some of the fields. Mirrors are represented by "\" and "/" characters. Arrangement of mirrors should make the light reach the sensor, while using minimum possible number of mirrors. You can't place mirrors on blocked fields, as well as on field with the laser and on field with the sensor. There is always a way for the light to reach the sensor.

Example

Input:

2
3 4
>...
###.
C...
5 5
v#...
.#.#.
.#.#.
.#.#.
...#C

Output:

>..\
###.
C../
v#/.

.#.#.
.#.#.
.#.#.
./#C