# [Solution] Fall Down solution codeforces

Fall Down solution codeforces – There is a grid with 𝑛n rows and 𝑚m columns, and three types of cells:

• An empty cell, denoted with ‘.‘.
• A stone, denoted with ‘*‘.
• An obstacle, denoted with the lowercase Latin letter ‘o‘.

## [Solution] Fall Down solution codeforces

All stones fall down until they meet the floor (the bottom row), an obstacle, or other stone which is already immovable. (In other words, all the stones just fall down as long as they can fall.)

Simulate the process. What does the resulting grid look like?

Input

The input consists of multiple test cases. The first line contains an integer 𝑡t (1𝑡1001≤t≤100) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers 𝑛n and 𝑚m (1𝑛,𝑚501≤n,m≤50) — the number of rows and the number of columns in the grid, respectively.

Then 𝑛n lines follow, each containing 𝑚m characters. Each of these characters is either ‘.‘, ‘*‘, or ‘o‘ — an empty cell, a stone, or an obstacle, respectively.

Output

For each test case, output a grid with 𝑛n rows and 𝑚m columns, showing the result of the process.

You don’t need to output a new line after each test, it is in the samples just for clarity.

Example
input

## [Solution] Fall Down solution codeforces

Copy
3
6 10
.*.*....*.
.*.......*
...o....o.
.*.*....*.
..........
.o......o*
2 9
...***ooo
.*o.*o.*o
5 5
*****
*....
*****
....*
*****


## [Solution] Fall Down solution codeforces

output

Copy
..........
...*....*.
.*.o....o.
.*........
.*......**
.o.*....o*

....**ooo
.*o**o.*o

.....
*...*
*****
*****
*****