Notes: For participants in the Prime Contest, please note that partial scores do not count as a solved problem during the contest. You must achieve a full score (100 points) for the problem to be considered solved.

A skating competition is ongoing. The rink is represented by an $n \times m$ grid, where . indicates passable ice, and # indicates obstacles that cannot be entered.

You start from a passable ice cell and performs a series of sliding actions. Each sliding action must follow these rules:

1. Choose a direction (up, down, left, right).
2. Slide continuously in the chosen direction until about to hit an obstacle or leave the rink boundaries, then stop.
3. After stopping, you can choose another direction to continue sliding.

Your task is to determine for each passable cell if it can serve as a starting point such that, following the above sliding rules, every passable cell on the rink can be visited at least once.

Note that you can pass through the same cell multiple times.

It is guaranteed there is at least one passable ice cell.

Input Format

The first line contains an integer $T$, representing the number of test cases.

For each test case:

The first line contains two integers, $n$ and $m$, indicating the number of rows and columns of the grid.

The next $n$ lines each contain $m$ characters: # represents an obstacle, . represents a passable cell.

Output Format

For each test case, output a modified version of the input grid with $n$ lines and $m$ characters each:

Replace each passable cell (.) that can be a valid starting point with *. Leave other cells unchanged (# remains an obstacle, other . cells cannot be starting points).

Sample Input 1

3
3 3
...
...
...
5 5
#....
.....
.....
.#.##
.....
10 3
...
##.
...
...
.#.
.#.
.#.
##.
...
...

Sample Output 1

.*.
***
.*.
#.*..
..*..
..*..
.#*##
..*..
...
##.
.*.
***
.#.
.#.
.#.
##.
...
...

Sample Input 2

3
9 11
....#######
.##.#######
.##.#.#####
......#####
###.#.#####
###.#.#####
##..#.#####
###.#......
###.##.....
10 3
#.#
...
..#
...
...
...
.#.
.#.
.#.
#..
4 11
....#######
.#.########
...........
#..........

Sample Output 2

....#######
.##.#######
.##.#.#####
......#####
###.#.#####
###.#.#####
##**#.#####
###.#......
###.##.....
#*#
.*.
**#
.*.
.*.
.*.
.#.
.#.
.#.
#..
..*.#######
.#*########
..*........
#.*........

Scoring

Notes: For participants in the Prime Contest, please note that partial scores do not count as a solved problem during the contest. You must achieve a full score (100 points) for the problem to be considered solved.

For all test cases: $1 \leq T \leq 10^5$, $n \times m \leq 2 \times 10^6$, $\sum n \times m \leq 4 \times 10^6$.