跳蚤王国的滑冰比赛 UNR（Universal Navigation on Rink）正在进行中。冰场被抽象为一个 $n \times m$ 的网格，其中 . 表示可通行的冰面，# 表示障碍，无法进入。
跳蚤从某个可通行的冰面出发，进行一系列滑行操作。每次滑行必须遵循以下规则：
- 选择一个方向（上、下、左、右）。
- 向该方向连续滑行，直到即将进入障碍或即将滑出边界时停止。
- 停下来后，可以重新选择一个方向继续滑行。
你的任务是：判断每一个可通行的冰面是否可以作为起点，使得从该点出发，按照上述滑行规则，能够经过所有的可通行的冰面至少一次，之后将可以作为起点的格子用 * 标记。
注意，跳蚤在滑行过程中可以多次经过同一个格子。
保证存在至少一个可通行的冰面。
输入格式
第一行一个整数 $T$，表示数据组数。
对于每组数据：
第一行两个整数 $n$ 和 $m$，表示网格的行数和列数。
接下来 $n$ 行，每行 $m$ 个字符，# 表示障碍，. 表示可通行格子。
输出格式
对于每组数据，输出一个由输入的网格进行修改得到的新网格，每次输出 $n$ 行，每行 $m$ 个字符：
如果某个 . 格子可以作为合法起点将其替换为 *，其余格子保持不变（# 仍为障碍，其他 . 表示不能作为起点）。
样例一
input
3
3 3
...
...
...
5 5
#....
.....
.....
.#.##
.....
10 3
...
##.
...
...
.#.
.#.
.#.
##.
...
...output
.*.
***
.*.
#.*..
..*..
..*..
.#*##
..*..
...
##.
.*.
***
.#.
.#.
.#.
##.
...
...样例二
input
3
9 11
....#######
.##.#######
.##.#.#####
......#####
###.#.#####
###.#.#####
##..#.#####
###.#......
###.##.....
10 3
#.#
...
..#
...
...
...
.#.
.#.
.#.
#..
4 11
....#######
.#.########
...........
#..........output
....#######
.##.#######
.##.#.#####
......#####
###.#.#####
###.#.#####
##**#.#####
###.#......
###.##.....
#*#
.*.
**#
.*.
.*.
.*.
.#.
.#.
.#.
#..
..*.#######
.#*########
..*........
#.*........样例三 $\sim$ 样例五
见附件下载。
数据范围
对于所有数据：$1 \leq T \leq 10^5,n\times m\le2\times10^6,\sum n \times m \leq 4\times10^6$。
| 子任务编号 | $n\times m\le$ | $\sum n \times m\le$ | 分值 |
|---|---|---|---|
| 1 | 10 | 100000 | 12 |
| 2 | 30 | 100000 | 12 |
| 3 | 100 | 100000 | 8 |
| 4 | 200 | 100000 | 8 |
| 5 | 500 | 500000 | 12 |
| 6 | 2000 | 2000000 | 8 |
| 7 | 5000 | 2000000 | 8 |
| 8 | 20000 | 2000000 | 8 |
| 9 | 100000 | 2000000 | 12 |
| 10 | 2000000 | 4000000 | 12 |
时间限制：$4\texttt{s}$
空间限制：$3.5\texttt{G}$