跳蚤王国的滑冰比赛 UNR（Universal Navigation on Rink）正在进行中。冰场被抽象为一个 $n \times m$ 的网格，其中 . 表示可通行的冰面，# 表示障碍，无法进入。

跳蚤从某个可通行的冰面出发，进行一系列滑行操作。每次滑行必须遵循以下规则：

1. 选择一个方向（上、下、左、右）。
2. 向该方向连续滑行，直到即将进入障碍或即将滑出边界时停止。
3. 停下来后，可以重新选择一个方向继续滑行。

你的任务是：判断每一个可通行的冰面是否可以作为起点，使得从该点出发，按照上述滑行规则，能够经过所有的可通行的冰面至少一次，之后将可以作为起点的格子用 * 标记。

注意，跳蚤在滑行过程中可以多次经过同一个格子。

保证存在至少一个可通行的冰面。

输入格式

第一行一个整数 $T$，表示数据组数。

对于每组数据：

第一行两个整数 $n$ 和 $m$，表示网格的行数和列数。

接下来 $n$ 行，每行 $m$ 个字符，# 表示障碍，. 表示可通行格子。

输出格式

对于每组数据，输出一个由输入的网格进行修改得到的新网格，每次输出 $n$ 行，每行 $m$ 个字符：

如果某个 . 格子可以作为合法起点将其替换为 *，其余格子保持不变（# 仍为障碍，其他 . 表示不能作为起点）。

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

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

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

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

样例三 $\sim$ 样例五

见附件下载。

数据范围

对于所有数据：$1 \leq T \leq 10^5,n\times m\le2\times10^6,\sum n \times m \leq 4\times10^6$。

时间限制：$4\texttt{s}$

空间限制：$3.5\texttt{G}$